cp's OEIS Frontend

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

%I A032198 #83 Jan 01 2025 23:31:53
%S A032198 1,3,6,13,25,58,121,283,646,1527,3601,8678,20881,50823,124054,304573,
%T A032198 750121,1855098,4600201,11442085,28527446,71292603,178526881,
%U A032198 447919418,1125750145,2833906683,7144450566,18036423973
%N A032198 "CIK" (necklace, indistinct, unlabeled) transform of 1,2,3,4,...
%H A032198 Vaclav Kotesovec, <a href="/A032198/b032198.txt">Table of n, a(n) for n = 1..1000</a>
%H A032198 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 A032198 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H A032198 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 A032198 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 A032198 P. Flajolet and M. Soria, <a href="/A032198/a032198.pdf">The Cycle Construction</a>. [pdf file]
%H A032198 Meghann Moriah Gibson, <a href="https://digitalcommons.georgiasouthern.edu/etd/1583/">Combinatorics of compositions</a>, Master of Science, Georgia Southern University, 2017.
%H A032198 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 A032198 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A032198 a(n) = 1/n*Sum_{d divides n} phi(n/d)*A004146(d). - _Vladeta Jovovic_, Feb 15 2003
%F A032198 From _Petros Hadjicostas_, Jan 07 2018: (Start)
%F A032198 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 A032198 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 A032198 G.f.: -2*x/(1 - x) - Sum_{n>=1} (phi(n)/n)*log(1 - 3*x^n + x^(2*n)).
%F A032198 (End)
%F A032198 From _Petros Hadjicostas_, Jun 19 2019: (Start)
%F A032198 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 A032198 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_{s >= 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 A032198 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 A032198 (End)
%e A032198 From _Petros Hadjicostas_, Jan 07 2018: (Start)
%e A032198 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 A032198 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 A032198 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 A032198 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 A032198 (End)
%t A032198 nmax = 30;
%t A032198 f[x_] = Sum[n*x^n, {n, 1, nmax}];
%t A032198 gf = Sum[(EulerPhi[n]/n)*Log[1/(1 - f[x^n])] + O[x]^nmax, {n, 1, nmax}]/x;
%t A032198 CoefficientList[gf, x] (* _Jean-François Alcover_, Jul 29 2018, after _Joerg Arndt_ *)
%o A032198 (PARI)
%o A032198 N = 66;  x = 'x + O('x^N);
%o A032198 f(x)=sum(n=1, N, n*x^n );
%o A032198 gf = sum(n=1, N, eulerphi(n)/n*log(1/(1-f(x^n)))  );
%o A032198 v = Vec(gf)
%o A032198 /* _Joerg Arndt_, Jan 21 2013 */
%Y A032198 Cf. A000032, A001906, A004146, A005248, A032170, A032287, A088305, A308723, A308747.
%Y A032198 Equals A005594(n) - 1.
%K A032198 nonn
%O A032198 1,2
%A A032198 _Christian G. Bower_