cp's OEIS Frontend

A308817 Total number of parts in all m-color dihedral compositions of n (that is, the total number of parts in all dihedral compositions of n where a part of size m may be colored with one of m colors).

%I A308817 #50 Feb 10 2025 03:12:14
%S A308817 1,4,10,26,56,138,299,726,1686,4158,10130,25678,64725,166538,428456,
%T A308817 1112226,2888604,7533750,19653903,51367462,134277878,351284164,
%U A308817 919080550,2405427698,6295780309,16480373968,43141303978,112939105716,295664584064,774042041090,2026429360115,5305210333758
%N A308817 Total number of parts in all m-color dihedral compositions of n (that is, the total number of parts in all dihedral compositions of n where a part of size m may be colored with one of m colors).
%C A308817 Cyclic compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation. These were first studied by Sommerville (1909).
%C A308817 Symmetric cyclic compositions or circular palindromes or achiral cyclic compositions are those cyclic compositions that have at least one axis of symmetry. They were also studied by Sommerville (1909, pp. 301-304).
%C A308817 Dihedral compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent iff one can be obtained from the other by rotation or reflection. See, for example, Knopfmacher and Robbins (2013).
%C A308817 The number of dihedral compositions of n (of any kind) is the average of the corresponding numbers of cyclic and symmetric cyclic compositions of n.
%C A308817 Let c = (c(m): m >= 1) be the input sequence and let b_k = (b_k(n): n >= 1) be the output sequence under Bower's DIK[k] ("bracelet, indistinct, unlabeled" with k boxes) transform of c; that is, b_k(n) = (DIK[k] c)_n for n >= 1. Hence, b_k(n) is the number of dihedral compositions of n with k parts, where a part of size m can be colored with one of c(m) colors. If C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence c, then the bivariate g.f. of the list of sequences (b_k: k >= 1) = ((DIK[k] c): k >= 1) = ((b_k(n): n >= 1): k >= 1) is Sum_{n,k >= 1} b_k(n)*x^n*y^k = (1 + y * C(x))^2/(4 * (1 - y^2 * C(x^2))) - (1/4) - (1/2) * Sum_{d >= 1} (phi(d)/d) * log(1 - y^d * C(x^d)).
%C A308817 Here, Sum_{k=1..n} k*b_k(n) is the total number of parts in all colored dihedral compositions of n (where the coloring of parts is done according to the input sequence c). To find the g.f. of the sequence (Sum_{k=1..n} k*b_k(n): n >= 1), we differentiate the above bivariate g.f. (i.e., Sum_{n,k >= 1} b_k(n)*x^n*y^k) w.r.t. y and set y = 1. We get (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d)).
%C A308817 For the current sequence, the input sequence is c(m) = m for m >= 1, and we are dealing with the so-called "m-color" compositions. m-color linear compositions were studied by Agarwal (2000), whereas m-color cyclic compositions were studied by Gibson (2017) and Gibson et al. (2018).
%C A308817 Thus, for the current sequence, a(n) is the total number of parts in all m-color dihedral compositions of n (where a part of size m may be colored with one of m colors). Since C(x) = x/(1 - x)^2, we get that (1 + C(x)) * (C(x) + C(x^2))/(2 * (1 - C(x^2))^2) + (1/2) * Sum_{d >= 1} phi(d) * C(x^d)/(1 - C(x^d))  = (1/2) * (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2) + (1/2) * Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)).
%H A308817 A. K. Agarwal, <a href="https://web.archive.org/web/20200714215813/https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005b15_1421.pdf">n-colour compositions</a>, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
%H A308817 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H A308817 Petros Hadjicostas, <a href="https://doi.org/10.2140/moscow.2020.9.173">Generalized colored circular palindromic compositions</a>, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
%H A308817 Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H A308817 Meghann Moriah Gibson, Daniel Gray, and Hua Wang, <a href="https://doi.org/10.1016/j.disc.2018.08.001">Combinatorics of n-color compositions</a>, Discrete Mathematics 341 (2018), 3209-3226.
%H A308817 Arnold Knopfmacher and Neville Robbins, <a href="https://www.researchgate.net/publication/260006088_Some_Properties_of_Dihedral_Compositions">Some properties of dihedral compositions</a>, Util. Math. 92 (2013), 207-220.
%H A308817 D. M. Y. Sommerville, <a href="https://doi.org/10.1112/plms/s2-7.1.263">On certain periodic properties of cyclic compositions of numbers</a>, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
%F A308817 a(n) = (A307415(n) + A308723(n))/2 for n >= 1.
%F A308817 a(n) = (n/10) * (11*F(n) + 7*F(n-1)) + (-1)^n * (n/10) * (-4*F(n) + 7*F(n-1)) - (1/5) * (5*F(n+1) + 3*F(n)) - (-1)^n * (1/5) * (3*F(n) - 5*F(n-1)) + (1/2) * Sum_{s|n} phi(n/s) * F(2*s) for n >= 1, where F(n) = A000045(n) (Fibonacci numbers).
%F A308817 G.f.: (1/2) * (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2) + (1/2) * Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)).
%e A308817 We have a(1) = 1 because 1_1 is the only m-color dihedral composition of n = 1 and the total number of parts is 1.
%e A308817 We have a(2) = 4 because 2_1, 2_2, 1_1 + 1_1 are all the m-color dihedral compositions of 2 and the total number of parts is 1 + 1 + 2 = 4.
%e A308817 We have a(3) = 10 because 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 1_1 + 1_1 + 1_1 are all the m-color dihedral compositions of n = 3 and the total number of parts is 1 + 1 + 1 + 2 + 2 + 3 = 10.
%e A308817 We have a(4) = 26 because 4_1, 4_2, 4_3, 4_4, 1_1 + 3_1, 1_1 + 3_2, 1_1 + 3_3, 2_1 + 2_1, 2_1 + 2_2, 2_2 + 2_2, 1_1 + 2_1 + 1_1, 1_1 + 2_2 + 1_1, 1_1 + 1_1 + 1_1 + 1_1 are all the m-color dihedral compositions of n = 4 and the total number of parts is 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 4 = 26.
%e A308817 Note that a(n) = A307415(n) = A308723(n) for n = 1, 2, 3, 4 because all cyclic compositions of n when 1 <= n <= 4 are symmetric as well (and thus are dihedral).
%e A308817 For n = 5, we have A307415(5) = 53 <> 59 = A308723(5), in which case, a(n) = (53 + 59)/2 = 56. For example, 1_1 + 2_1 + 3_1 is a dihedral composition of n = 5, but it is not symmetric, so it corresponds to two (inequivalent) cyclic compositions: 1_1 + 2_1 + 3_1 and 3_1 + 2_1 + 1_1. Similarly, 1_1 + 2_1 + 2_2 is a dihedral composition of n = 5, but it is not symmetric, so it corresponds to two (inequivalent) cyclic compositions: 1_1 + 2_1 + 2_2 and 2_2 + 2_1 + 1_1.
%Y A308817 Cf. A000045, A030267, A032198, A032287, A088305, A307415, A308723.
%K A308817 nonn
%O A308817 1,2
%A A308817 _Petros Hadjicostas_, Jun 26 2019