The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A008965 Number of necklaces of sets of beads containing a total of n beads. 141
 1, 2, 3, 5, 7, 13, 19, 35, 59, 107, 187, 351, 631, 1181, 2191, 4115, 7711, 14601, 27595, 52487, 99879, 190745, 364723, 699251, 1342183, 2581427, 4971067, 9587579, 18512791, 35792567, 69273667, 134219795, 260301175, 505294127, 981706831, 1908881899, 3714566311, 7233642929 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. Equivalently, a(n) is the number of cyclic compositions of n. These could also be loosely described as cyclic partitions. REFERENCES Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520, Table 8.13. LINKS Vincenzo Librandi, Table of n, a(n) for n = 1..1000 R. Bekes, J. Pedersen and B. Shao, Mad tea party cyclic partitions, College Math. J., 43 (2012), 24-36. P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs., Vol. 3 (2000), #00.1.5. Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, and Qiang Wang, A Graph Joining Greedy Approach to Binary de Bruijn Sequences, arXiv:2004.09810 [cs.IT], 2020. P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60. P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60. P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 48. Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2. FORMULA a(n) = A000031(n-1) - 1. 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 EXAMPLE E.g. the 5 necklaces for n=4 are (3, 1), (4), (1, 1, 1, 1), (2, 1, 1), (2, 2). 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)). For n=6 the 13 necklaces are .1:  (1, 1, 1, 1, 1, 1), .2:  (2, 1, 1, 1, 1), .3:  (2, 1, 2, 1). .4:  (2, 2, 1, 1), .5:  (2, 2, 2), .6:  (3, 1, 1, 1), .7:  (3, 1, 2), .8:  (3, 2, 1), .9:  (3, 3), 10:  (4, 1, 1), 11:  (4, 2), 12:  (5, 1), 13:  (6). [corrected by Marcel Vonk (mail(AT)marcelvonk.nl), Feb 05 2008] MAPLE with(combstruct): seq(combstruct[count]([ N, {N=Cycle(Set(Z, card>=1))}, unlabeled ], size=n), n=1..100); MATHEMATICA 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 *) 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 *) PROG (PARI) N=66;  x='x+O('x^N); B(x)=x/(1-x); A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k)))); Vec(A) /* Joerg Arndt, Aug 06 2012 */ CROSSREFS Row sums of A037306. Cf. A000031. Sequence in context: A138184 A236340 A273161 * A113864 A188754 A108310 Adjacent sequences:  A008962 A008963 A008964 * A008966 A008967 A008968 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 19 01:17 EDT 2020. Contains 337175 sequences. (Running on oeis4.)