|
|
A008965
|
|
Number of necklaces of sets of beads containing a total of n beads.
|
|
181
|
|
|
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
|
|
|
FORMULA
|
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
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.
Dirichlet g.f.: zeta(s) * (f(s+1)/zeta(s+1) - 1), where f(s) = Sum_{n>=1} 2^n/n^s. (End)
|
|
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
|
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)
(Python)
from sympy import totient, divisors
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|