A008965 Number of necklaces of sets of beads containing a total of n beads.

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

Offset: 1

Author

Paul Zimmermann

Keywords

• nonn
• easy
• nice

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.

Inverse Mobius transform of A059966. - Jianing Song, Nov 13 2021

This sequence seems to represent the number of modal families (i.e., sets of scales who are each other's modes) in a musical tuning with n notes per octave. - Luke Knotts, May 28 2025

Examples

			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]
		

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.
• Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.
• 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.
• Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021.
• Index entries for sequences related to necklaces

Crossrefs

Row sums of A037306. CIK transform of A057427.

Cf. A000031.

Programs

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 *)

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

Python

from sympy import totient, divisors
def A008965(n): return sum(totient(d)*(1<Chai Wah Wu, Sep 23 2023

Formula

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

From Jianing Song, Nov 13 2021: (Start)

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)