|
%I #48 Feb 11 2021 21:22:58
%S 1,4,10,26,59,160,383,1018,2606,6836,17721,46580,121405,318212,832190,
%T 2179358,5702903,14933264,39088187,102341134,267915110,701426484,
%U 1836311925,4807575700,12586269265,32951401540,86267576506,225851752438,591286729907,1548009602240,4052739537911
%N Total number of parts in all m-cyclic compositions of n (where each part of size m can be colored with one of m colors).
%C Unmarked cyclic compositions (originally studied by Sommerville (1909)) 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.
%C The so-called "m-cyclic compositions" of n are cyclic compositions of n such that each part of size m can be colored with any one of m colors. (Colored ordered partitions were originally introduced by Agarwal (2000). The theory of Bower about transforms in the web link below is a generalization of this idea.)
%C If b(n) is the number of m-colored compositions of n, then (b(n): n >= 1) is the CIK transform of the sequence 1, 2, 3, ... and it has the g.f. -sum_{n >= 1} (phi(s)/s) * log(1 - C(x^s)), where C(x) = x + 2*x^2 + 3*x^3 + 4*x^4 + ... = x/(1-x)^2. (See Bower's link about transforms for information about the CIK transform.) Thus, b(n) = A032198(n) for n >= 1, and its g.f. and formula were also derived in Gibson (2017) and Gibson et al. (2018).
%C In general, if c = (c(m): m >= 1) is the input sequence and (b_k(n): n >= 1) is the output sequence under the CIK[k] transform of c, then b_n = (CIK c)_n = Sum_{k = 1..n} (CIK[k] c)_n = Sum_{k = 1..n} b_k(n) for all n >= 1 (see Bower's web link on transforms).
%C The g.f. of (b_k(n): n >= 1) is Sum_{n >= 1} b_k(n)*x^k = (1/k)*Sum_{d|k} phi(d) * A(x^d)^(k/d). It follows that Sum_{n >= 1, k >= 1} b_k(n)*x^n*y^k = -Sum_{d >= 1} (phi(d)/d) * log(1 - y^d *A(x^d)) (with the understanding that b_k(n) = 0 for k > n).
%C For n >= 1, let d(n) = Sum_{k >= 1} k*b_k(n) = total number of parts of in all compositions of n under the CIK transform of c = (c(m): m >= 1). Thus, d(n) is the total number of parts in all cyclic compositions of n where each part of size m can be colored with c(m) colors.
%C To obtain the g.f. of (d(n): n >= 1) = (Sum_{k = 1..n} k*b_k(n): n >= 1), we differentiate the bivariate g.f. Sum_{n >= 1, k >= 1} b_k(n)*x^n*y^k w.r.t. y and set y = 1. We get Sum_{n >= 1} d(n)*x^n = Sum_{d >= 1} phi(d) * A(x^d)/(1 - A(x^d)).
%C In our case, A(x) = x/(1 - x)^2, so Sum_{n >= 1} d(n)*x^n = -Sum_{d >=1} phi(d) * x^d/(1 - 3*x^d + x^(2*d)), which is exactly the g.f. of the current sequence that was proved in Gibson (2017) and Gibson et al. (2018).
%C (End)
%H 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 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H 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 D. M. Y. Sommerville, <a href="http://onlinelibrary.wiley.com/doi/10.1112/plms/s2-7.1.263/abstract">On certain periodic properties of cyclic compositions of numbers</a>, Proc. London Math. Soc., S2-7(1) (1909), 263-313.
%F a(n) = Sum_{s|n} phi(s)*A088305(n/s) = Sum_{s|n} phi(n/s)*Fibonacci(2*s) for n >= 1. (See Theorem 3.1 in Gibson et al. (2018).)
%F a(n) ~ (2/(3 - sqrt(5)))^n/sqrt(5) for large n. (See p. 3210 in Gibson et al. (2018).)
%F G.f.: Sum_{s >= 1} phi(s) * x^s/(1 - 3*x^s + x^(2*s)). (See Eq. (1.2) in Gibson et al. (2018).)
%e We have a(1) = 1 because 1_1 is the only m-color cyclic composition of n = 1 and the total number of parts is 1.
%e We have a(2) = 4 because 2_1, 2_2, 1_1 + 1_1 are all the m-color cyclic compositions of 2 and the total number of parts is 1 + 1 + 2 = 4.
%e 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 cyclic compositions of n = 3 and the total number of parts is 1 + 1 + 1 + 2 + 2 + 3 = 10.
%e 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 cyclic 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.
%Y Cf. A001906, A032198, A088305.
%K nonn
%O 1,2
%A _Petros Hadjicostas_, Jun 19 2019
| 