%I #106 Mar 09 2024 12:32:42
%S 1,2,3,5,7,13,19,35,59,107,187,351,631,1181,2191,4115,7711,14601,
%T 27595,52487,99879,190745,364723,699251,1342183,2581427,4971067,
%U 9587579,18512791,35792567,69273667,134219795,260301175,505294127,981706831,1908881899,3714566311,7233642929
%N Number of necklaces of sets of beads containing a total of n beads.
%C A necklace of sets of beads is a cycle where each element of the cycle is itself a set of beads, the total size being the total number of beads.
%C Equivalently, a(n) is the number of cyclic compositions of n. These could also be loosely described as cyclic partitions.
%C Inverse Mobius transform of A059966. - _Jianing Song_, Nov 13 2021
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520, Table 8.13.
%H Vincenzo Librandi, <a href="/A008965/b008965.txt">Table of n, a(n) for n = 1..1000</a>
%H R. Bekes, J. Pedersen and B. Shao, <a href="http://dx.doi.org/10.4169/college.math.j.43.1.025">Mad tea party cyclic partitions</a>, College Math. J., 43 (2012), 24-36.
%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. 17.
%H P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs., Vol. 3 (2000), #00.1.5.
%H Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, and Qiang Wang, <a href="https://arxiv.org/abs/2004.09810">A Graph Joining Greedy Approach to Binary de Bruijn Sequences</a>, arXiv:2004.09810 [cs.IT], 2020.
%H P. Flajolet and M. Soria, <a href="https://epubs.siam.org/doi/abs/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Flajolet and M. Soria, <a href="/A008965/a008965.pdf">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 48.
%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), #16.8.2.
%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/etd/2273">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021.
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = A000031(n) - 1.
%F G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x)=x/(1-x); see the Flajolet/Soria reference. - _Joerg Arndt_, Aug 06 2012
%F From _Jianing Song_, Nov 13 2021: (Start)
%F a(n) = Sum_{d|(2^n-1)} phi(d)/ord(2,d), where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d.
%F Dirichlet g.f.: zeta(s) * (f(s+1)/zeta(s+1) - 1), where f(s) = Sum_{n>=1} 2^n/n^s. (End)
%e E.g. the 5 necklaces for n=4 are (3, 1), (4), (1, 1, 1, 1), (2, 1, 1), (2, 2).
%e In the Combstruct language these can be described as Cycle(Set(Z), Set(Z), Set(Z), Set(Z)), Cycle(Set(Z, Z), Set(Z), Set(Z)), Cycle(Set(Z, Z, Z, Z)), Cycle(Set(Z, Z), Set(Z, Z)), Cycle(Set(Z), Set(Z, Z, Z)).
%e For n=6 the 13 necklaces are
%e 1: (1, 1, 1, 1, 1, 1),
%e 2: (2, 1, 1, 1, 1),
%e 3: (2, 1, 2, 1),
%e 4: (2, 2, 1, 1),
%e 5: (2, 2, 2),
%e 6: (3, 1, 1, 1),
%e 7: (3, 1, 2),
%e 8: (3, 2, 1),
%e 9: (3, 3),
%e 10: (4, 1, 1),
%e 11: (4, 2),
%e 12: (5, 1),
%e 13: (6).
%e [corrected by Marcel Vonk (mail(AT)marcelvonk.nl), Feb 05 2008]
%p with(combstruct): seq(combstruct[count]([ N,{N=Cycle(Set(Z,card>=1))},unlabeled ], size=n), n=1..100);
%t a[n_] := Sum[ EulerPhi[d]*2^(n/d), {d, Divisors[n]}]/n-1; Table[a[n], {n, 1, 38}] (* _Jean-François Alcover_, Sep 04 2012, from A000031 *)
%t nn=35; Drop[Apply[Plus,Table[CoefficientList[Series[CycleIndex[ CyclicGroup[n],s]/.Table[s[i]->x^i/(1-x^i),{i,1,n}],{x,0,nn}],x],{n,1,nn}]],1] (* _Geoffrey Critzer_, Oct 30 2012 *)
%o (PARI)
%o N=66; x='x+O('x^N);
%o B(x)=x/(1-x);
%o A=sum(k=1,N,eulerphi(k)/k*log(1/(1-B(x^k))));
%o Vec(A)
%o /* _Joerg Arndt_, Aug 06 2012 */
%o (Python)
%o from sympy import totient, divisors
%o def A008965(n): return sum(totient(d)*(1<<n//d) for d in divisors(n, generator=True))//n-1 # _Chai Wah Wu_, Sep 23 2023
%Y Row sums of A037306.
%Y Cf. A000031.
%K nonn,easy,nice
%O 1,2
%A _Paul Zimmermann_