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).

1, 4, 10, 26, 56, 138, 299, 726, 1686, 4158, 10130, 25678, 64725, 166538, 428456, 1112226, 2888604, 7533750, 19653903, 51367462, 134277878, 351284164, 919080550, 2405427698, 6295780309, 16480373968, 43141303978, 112939105716, 295664584064, 774042041090, 2026429360115, 5305210333758

Offset: 1

Author

Petros Hadjicostas, Jun 26 2019

Keywords

• nonn

Comments

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).

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).

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).

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.

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)).

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)).

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).

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)).

Examples

			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.
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.
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.
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.
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).
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.
		

Links

• A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
• C. G. Bower, Transforms (2).
• Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
• Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
• Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
• Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
• D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Crossrefs

Cf. A000045, A030267, A032198, A032287, A088305, A307415, A308723.

Formula

a(n) = (A307415(n) + A308723(n))/2 for n >= 1.

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).

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)).