A307415 Total number of parts in all symmetric m-color cyclic compositions of n (that is, the total number of parts in all achiral cyclic compositions of n where a part with size m can be colored with one of m colors).

1, 4, 10, 26, 53, 116, 215, 434, 766, 1480, 2539, 4776, 8045, 14864, 24722, 45094, 74305, 134236, 219619, 393790, 640646, 1141844, 1849175, 3279696, 5291353, 9346396, 15031450, 26458994, 42438221, 74479940, 119182319, 208629386, 333170830, 581904544, 927617347, 1616924664

Offset

1,2

Comments

Cyclic compositions of a positive integer n are equivalence classes of ordered partitions of n such that two such partitions are equivalent if 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).

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 CPAL[k] (circular palindrome with k boxes) transform of c; that is, b_k(n) = (CPAC[k] c)_n for n >= 1. Hence, b_k(n) is the number of symmetric cyclic 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) = ((CPAL[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/(2 * (1 - y^2*C(x^2))) - (1/2).

Here, Sum_{k=1..n} k*b_k(n) is the total number of parts in all symmetric colored cyclic 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))/(1 - C(x^2))^2.

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 symmetric (achiral) m-color cyclic 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))/(1 - C(x^2))^2 = (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2).

The roots of the denominator (x^2 + x - 1)^2 * (x^2 - x - 1)^2 are phi, -phi, 1/phi, -1/phi, where phi = (1 + sqrt(5))/2 = A001622 is the golden ratio. Each of these roots is double, so a(n) = (c_1 + d_1*n) * phi^n + (c_2 + d_2*n) * (-phi)^n + (c_3 + d_3*n) * (1/phi)^n + (c_4 + d_4*n) * (-1/phi)^n, and the constants c_i, d_i (i = 1, 2, 3, 4) can be determined from the first eight terms of (a(n): n >= 1). Since, however, the Fibonacci numbers (A000045(n): n >= 0) can be expressed in terms of phi, after some tedious algebra, we may derive the formula given below.

Links

Table of n, a(n) for n=1..36.

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.

D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Formula

a(n) = (n/5) * (11*F(n) + 7*F(n-1)) + (-1)^n * (n/5) * (-4*F(n) + 7*F(n-1)) - (2/5) * (5*F(n+1) + 3*F(n)) - (-1)^n * (2/5) * (3*F(n) - 5*F(n-1)) for n >= 1, where F(n) = A000045(n) is the n-th Fibonacci number.

G.f.: (x^2 - x + 1) * x * (x^2 + 3*x + 1) * (x + 1)^2/((x^2 + x - 1)^2 * (x^2 - x - 1)^2).

Example

We have a(1) = 1 because we only have one symmetric cyclic composition of n = 1, namely 1_1, which has 1 part.
We have a(2) = 4 because we have the following colored achiral cyclic compositions of n = 2: 2_1, 2_2, 1_1 + 1_1; hence, a(2) = 1 + 1 + 2 = 4.
We have a(3) = 10 because we have the following colored achiral cyclic compositions of n = 3: 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 1_1 + 1_1 + 1_1; hence, a(3) = 1 + 1 + 1 + 2 + 2 + 3 = 10.
We have a(4) = 26 because we have the following colored achiral cyclic compositions of n = 4: 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; hence, a(4) = 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 4 = 26.
We have a(5) = 53 because we have the following colored achiral cyclic compositions of n = 5:
(i) With one part: 5_1, 5_2, 5_3, 5_4, 5_5; i.e., a total of 5 parts.
(ii) With two parts: 1_1 + 4_1, 1_1 + 4_2, 1_1 + 4_3, 1_1 + 4_4, 2_1 + 3_1, 2_1 + 3_2, 2_1 + 3_3, 2_2 + 3_1, 2_2 + 3_2, 2_2 + 3_3; i.e., a total of 20 parts.
(iii) With three parts: 1_1 + 3_1 + 1_1, 1_1 + 3_2 + 1_1, 1_1 + 3_3 + 1_1, 2_1 + 1_1 + 2_1, 2_2 + 1_1 + 2_2; i.e., a total of 15 parts.
(iv) With four parts: 1_1 + 1_1 + 2_1 + 1_1, 1_1 + 1_1 + 2_2 + 1_1 (here, the axis of symmetry passes through one of the 1's and through 2); i.e., a total of 8 parts.
(v) With five parts: 1_1 + 1_1 + 1_1 + 1_1 + 1_1; i.e., a total of 5 parts.
Thus, a(5) = 5 + 20 + 15 + 8 + 5 = 53.

Crossrefs

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

Sequence in context: A001214 A200455 A269064 * A322060 A022812 A192306

Adjacent sequences: A307412 A307413 A307414 * A307416 A307417 A307418

Keyword

nonn

Author

Petros Hadjicostas, Jun 24 2019

Status

approved