login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008965 Number of necklaces of sets of beads containing a total of n beads. 50

%I

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

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

%F a(n) = A000031(n-1) - 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

%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 */

%Y Row sums of A037306.

%Y Cf. A000031.

%K nonn,easy,nice

%O 1,2

%A _Paul Zimmermann_

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 21:59 EST 2019. Contains 320200 sequences. (Running on oeis4.)