cp's OEIS Frontend

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

%I A307415 #54 Feb 11 2021 21:23:46
%S A307415 1,4,10,26,53,116,215,434,766,1480,2539,4776,8045,14864,24722,45094,
%T A307415 74305,134236,219619,393790,640646,1141844,1849175,3279696,5291353,
%U A307415 9346396,15031450,26458994,42438221,74479940,119182319,208629386,333170830,581904544,927617347,1616924664
%N 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).
%C A307415 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).
%C A307415 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 A307415 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).
%C A307415 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.
%C A307415 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 A307415 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).
%C A307415 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.
%H A307415 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 A307415 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H A307415 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 A307415 Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H A307415 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 A307415 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 A307415 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.
%F A307415 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).
%e A307415 We have a(1) = 1 because we only have one symmetric cyclic composition of n = 1, namely 1_1, which has 1 part.
%e A307415 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.
%e A307415 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.
%e A307415 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.
%e A307415 We have a(5) = 53 because we have the following colored achiral cyclic compositions of n = 5:
%e A307415 (i) With one part: 5_1, 5_2, 5_3, 5_4, 5_5; i.e., a total of 5 parts.
%e A307415 (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.
%e A307415 (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.
%e A307415 (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.
%e A307415 (v) With five parts: 1_1 + 1_1 + 1_1 + 1_1 + 1_1; i.e., a total of 5 parts.
%e A307415 Thus, a(5) = 5 + 20 + 15 + 8 + 5 = 53.
%Y A307415 Cf. A000045, A001622, A030267, A032198, A032287, A088305, A308723.
%K A307415 nonn
%O A307415 1,2
%A A307415 _Petros Hadjicostas_, Jun 24 2019