|
| |
|
|
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).
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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).
(End)
|
|
|
LINKS
|
|
|
|
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).)
|
|
|
EXAMPLE
|
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.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
