A308747 Number of achiral m-color cyclic compositions of n (that is, number of cyclic compositions of n with reflection symmetry where each part of size m can be colored with one of m colors).

1, 3, 6, 13, 23, 44, 73, 131, 210, 365, 575, 984, 1537, 2611, 4062, 6877, 10679, 18052, 28009, 47315, 73386, 123933, 192191, 324528, 503233, 849699, 1317558, 2224621, 3449495, 5824220, 9030985, 15248099, 23643522, 39920141, 61899647, 104512392, 162055489, 273617107

Offset: 1

Author

Petros Hadjicostas, Jun 21 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 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(m): m >= 1) be the input sequence and let b = (b(n): n >= 1) be the output sequence under the CPAL (circular palindrome) transform of c; that is, b(n) = (CPAC c)n for n >= 1. Hence, b(n) is the number of symmetric cyclic compositions of n 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 g.f. of b = (CPAL c) is Sum_{n >= 1} b(n)*x^n = (1 + C(x))^2/(2 * (1 - C(x^2))) - (1/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 number of symmetric (achiral) cyclic compositions of n where a part of size m may be colored with one of m colors (for each m >= 1).

The function A(x) = (exp(Pi*(x + 1)*I)*phi^(-x - 4) - exp(2*I*Pi*x)*phi^(4 - x) + exp(Pi*x*I)*phi^(x - 4) + phi^(x + 4))/sqrt(5) - 2*x, where phi is the golden ratio, shows that the sequence can be easily extended to all integers. - Peter Luschny, Aug 09 2020

Examples

			We have a(1) = 1 because we only have one symmetric cyclic composition of n = 1, namely 1_1 (and a part of size 1 can be colored with only one color).
We have a(2) = 3 because we have the following colored achiral cyclic compositions of n = 2: 2_1, 2_2, 1_1 + 1_1.
We have a(3) = 6 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.
We have a(4) = 13 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.
We have a(5) = 23 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;
(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;
(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;
(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);
(v) with five parts: 1_1 + 1_1 + 1_1 + 1_1 + 1_1.
		

Links

• A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
• Christian 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.

Crossrefs

Cf. A000045, A001906, A005594, A032198, A032287, A088305.

Formula

CPAL (circular palindrome) transform of 1, 2, 3, 4, ...

a(n) = 2*a(n - 1) + 2*a(n - 2) - 6*a(n - 3) + 2*a(n - 4) + 2*a(n - 5) - a(n - 6) for n >= 7 with a(1) = 1, a(2) = 3, a(3) = 6, a(4) = 13, a(5) = 23, and a(6) = 44.

a(n) = 3*a(n - 2) - a(n - 4) + 2*(n - 2) for n >= 5 with a(1) = 1, a(2) = 3, a(3) = 6, and a(4) = 13.

a(n) = Fib(n + 4) + (-1)^n * Fib(n - 4) - 2*n for n >= 4, where Fib(n) = A000045(n).

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