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

1, 4, 10, 26, 59, 160, 383, 1018, 2606, 6836, 17721, 46580, 121405, 318212, 832190, 2179358, 5702903, 14933264, 39088187, 102341134, 267915110, 701426484, 1836311925, 4807575700, 12586269265, 32951401540, 86267576506, 225851752438, 591286729907, 1548009602240, 4052739537911

Offset: 1

Author

Petros Hadjicostas, Jun 19 2019

Keywords

• nonn
• changed

Comments

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.

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

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

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

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

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.

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

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

Examples

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

Links

• A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math., 31(11) (2000), 1421-1427.
• C. G. Bower, Transforms (2).
• 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. A001906, A032198, A088305.

Formula

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

a(n) ~ (2/(3 - sqrt(5)))^n/sqrt(5) for large n. (See p. 3210 in Gibson et al. (2018).)

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