1,2

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.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Index entries for sequences related to necklaces

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 48

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 (2, 3, 1), (2, 1, 1, 1, 1), (2, 2, 2), (2, 4), (3, 3), (4, 1, 1), (1, 1, 1, 1, 1, 1), (3, 1, 1, 1), (2, 2, 1, 1), (1, 5), (2, 1, 3), (6), (2, 1, 2, 1). [Example corrected by Marcel Vonk (mail(AT)marcelvonk.nl), Feb 05 2008]

with(combstruct): seq(combstruct[count]([ N, {N=Cycle(Set(Z, card>=1))}, unlabeled ], size=n), n=1..100);

a(n) = A000031(n) - 1 allowing different offsets.

Sequence in context: A075580 A077132 A138184 this_sequence A113864 A108310 A146999

Adjacent sequences: A008962 A008963 A008964 this_sequence A008966 A008967 A008968

nonn,easy,nice

Paul.Zimmermann(AT)loria.fr