A032198 - OEIS

%I #80 Aug 06 2024 21:33:46

%S 1,3,6,13,25,58,121,283,646,1527,3601,8678,20881,50823,124054,304573,

%T 750121,1855098,4600201,11442085,28527446,71292603,178526881,

%U 447919418,1125750145,2833906683,7144450566,18036423973

%N "CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,...

%H Vaclav Kotesovec, <a href="/A032198/b032198.txt">Table of n, a(n) for n = 1..1000</a>

%H A. K. Agarwal, <a href="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 Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 31.

%H P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/publist.html">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

%H P. Flajolet and M. Soria, <a href="/A032198/a032198.pdf">The Cycle Construction</a>. [pdf file]

%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 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F a(n) = 1/n*Sum_{d divides n} phi(n/d)*A004146(d). - _Vladeta Jovovic_, Feb 15 2003

%F From _Petros Hadjicostas_, Jan 07 2018: (Start)

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

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

%F G.f.: -2*x/(1 - x) - Sum_{n>=1} (phi(n)/n)*log(1 - 3*x^n + x^(2*n)).

%F (End)

%F From _Petros Hadjicostas_, Jun 19 2019: (Start)

%F 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, ...

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

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

%F (End)

%e From _Petros Hadjicostas_, Jan 07 2018: (Start)

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

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

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

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

%e (End)

%t nmax = 30;

%t f[x_] = Sum[n*x^n, {n, 1, nmax}];

%t gf = Sum[(EulerPhi[n]/n)*Log[1/(1 - f[x^n])] + O[x]^nmax, {n, 1, nmax}]/x;

%t CoefficientList[gf, x] (* _Jean-François Alcover_, Jul 29 2018, after _Joerg Arndt_ *)

%o (PARI)

%o N = 66;  x = 'x + O('x^N);

%o f(x)=sum(n=1, N, n*x^n );

%o gf = sum(n=1, N, eulerphi(n)/n*log(1/(1-f(x^n)))  );

%o v = Vec(gf)

%o /* _Joerg Arndt_, Jan 21 2013 */

%Y Cf. A000032, A001906, A004146, A005248, A032170, A032287, A088305, A308723, A308747.

%Y Equals A005594(n) - 1.

%K nonn

%O 1,2

%A _Christian G. Bower_