|
| |
|
|
A032198
|
|
"CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,...
|
|
13
|
|
|
|
1, 3, 6, 13, 25, 58, 121, 283, 646, 1527, 3601, 8678, 20881, 50823, 124054, 304573, 750121, 1855098, 4600201, 11442085, 28527446, 71292603, 178526881, 447919418, 1125750145, 2833906683, 7144450566, 18036423973
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = -2 + (1/n)*Sum_{d|n} phi(n/d)*A005248(d) = -2 + (1/n)*Sum_{d|n} phi(n/d)*L(2*d), where L(n) = A000032(n) is the usual Lucas sequence.
G.f.: -Sum_{n >= 1} (phi(n)/n)*log(1 - B(x^n)), where B(x) = x + 2*x^2 + 3*x^3 + 4*x^4 + ... = x/(1-x)^2.
G.f.: -2*x/(1 - x) - Sum_{n>=1} (phi(n)/n)*log(1 - 3*x^n + x^(2*n)).
(End)
According to Gibson et al. (2018), a(n) is the number of m-color cyclic compositions of n where each part of size m has m possible colors. This is nothing else than the CIK transform of the sequence 1, 2, 3, 4, ...
Using the theory of Flajolet and Soria (1991), Gibson et al. (2018, Eq. (1.1)) proved that the g.f. of a(n) is Sum_{n >= 1} (phi(s)/s) * log((1 - x^s)^2/(1 - 3*x^s + x^(2*s)), which is exactly the same g.f. as the ones above.
Gibson et al. (2018, p. 3210) also proved that a(n) ~ (2/(3 -sqrt(5))^n/n for large n. See also Chapter 3 in Gibson (2017).
(End)
|
|
|
EXAMPLE
|
We give some examples to illustrate the theory of C. G. Bower about transforms given in the weblink above. We assume we have boxes of different sizes and colors that we place on a circle to form a necklace. Two boxes of the same size and same color are considered identical (indistinct and unlabeled). We do, however, change the roles of the sequences (a(n): n>=1) and (b(n): n>=1) that appear in the weblink above. We assume (a(n): n>=1) = CIK((b(n): n>=1)).
Since b(1) = 1, b(2) = 2, b(3) = 3, etc., a box that can hold 1 ball only can be of 1 color only, a box that can hold 2 balls only can be one of 2 colors only, a box that can hold 3 balls can be one of 3 colors, and so on.
To prove that a(3) = 6, we consider three cases. In the first case, we have a single box that can hold 3 balls, and thus we have 3 possibilities for the 3 colors the box can be. In the second case, we have a box that can hold 2 balls and a box that can hold 1 ball. Here, we have 2 x 1 = 2 possibilities. In the third case, we have 3 identical boxes, each of which can hold 1 ball. This gives rise to 1 possibility. Hence, a(3) = 3 + 2 + 1 = 6.
To prove that a(4) = 13, we consider 5 cases: a box with 4 balls (4 possibilities), one box with 3 balls and one box with 1 ball (3 possibilities), two identical boxes each with 2 balls (3 possibilities), one box with 2 balls and two identical boxes each with 1 ball (2 possibilities), and four identical boxes each with 1 ball (1 possibility). Thus, a(4) = 4 + 3 + 3 + 2 + 1 = 13.
(End)
|
|
|
MATHEMATICA
|
nmax = 30;
f[x_] = Sum[n*x^n, {n, 1, nmax}];
gf = Sum[(EulerPhi[n]/n)*Log[1/(1 - f[x^n])] + O[x]^nmax, {n, 1, nmax}]/x;
|
|
|
PROG
|
(PARI)
N = 66; x = 'x + O('x^N);
f(x)=sum(n=1, N, n*x^n );
gf = sum(n=1, N, eulerphi(n)/n*log(1/(1-f(x^n))) );
v = Vec(gf)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
