cp's OEIS Frontend

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

%I A008965 #116 Jun 02 2025 02:30:38
%S A008965 1,2,3,5,7,13,19,35,59,107,187,351,631,1181,2191,4115,7711,14601,
%T A008965 27595,52487,99879,190745,364723,699251,1342183,2581427,4971067,
%U A008965 9587579,18512791,35792567,69273667,134219795,260301175,505294127,981706831,1908881899,3714566311,7233642929
%N A008965 Number of necklaces of sets of beads containing a total of n beads.
%C A008965 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 A008965 Equivalently, a(n) is the number of cyclic compositions of n. These could also be loosely described as cyclic partitions.
%C A008965 Inverse Mobius transform of A059966. - _Jianing Song_, Nov 13 2021
%C A008965 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
%D A008965 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 520, Table 8.13.
%H A008965 Vincenzo Librandi, <a href="/A008965/b008965.txt">Table of n, a(n) for n = 1..1000</a>
%H A008965 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 A008965 Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.
%H A008965 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 A008965 Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, and Qiang Wang, <a href="https://arxiv.org/abs/2004.09810">A Graph Joining Greedy Approach to Binary de Bruijn Sequences</a>, arXiv:2004.09810 [cs.IT], 2020.
%H A008965 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 A008965 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 A008965 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 48.
%H A008965 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 A008965 Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/etd/2273">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021.
%H A008965 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A008965 a(n) = A000031(n) - 1.
%F A008965 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
%F A008965 From _Jianing Song_, Nov 13 2021: (Start)
%F A008965 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.
%F A008965 Dirichlet g.f.: zeta(s) * (f(s+1)/zeta(s+1) - 1), where f(s) = Sum_{n>=1} 2^n/n^s. (End)
%e A008965 E.g. the 5 necklaces for n=4 are (3, 1), (4), (1, 1, 1, 1), (2, 1, 1), (2, 2).
%e A008965 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 A008965 For n=6 the 13 necklaces are
%e A008965    1:  (1, 1, 1, 1, 1, 1),
%e A008965    2:  (2, 1, 1, 1, 1),
%e A008965    3:  (2, 1, 2, 1),
%e A008965    4:  (2, 2, 1, 1),
%e A008965    5:  (2, 2, 2),
%e A008965    6:  (3, 1, 1, 1),
%e A008965    7:  (3, 1, 2),
%e A008965    8:  (3, 2, 1),
%e A008965    9:  (3, 3),
%e A008965   10:  (4, 1, 1),
%e A008965   11:  (4, 2),
%e A008965   12:  (5, 1),
%e A008965   13:  (6).
%e A008965 [corrected by Marcel Vonk (mail(AT)marcelvonk.nl), Feb 05 2008]
%p A008965 with(combstruct): seq(combstruct[count]([ N,{N=Cycle(Set(Z,card>=1))},unlabeled ], size=n), n=1..100);
%t A008965 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 A008965 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 A008965 (PARI)
%o A008965 N=66;  x='x+O('x^N);
%o A008965 B(x)=x/(1-x);
%o A008965 A=sum(k=1,N,eulerphi(k)/k*log(1/(1-B(x^k))));
%o A008965 Vec(A)
%o A008965 /* _Joerg Arndt_, Aug 06 2012 */
%o A008965 (Python)
%o A008965 from sympy import totient, divisors
%o A008965 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
%Y A008965 Row sums of A037306. CIK transform of A057427.
%Y A008965 Cf. A000031.
%K A008965 nonn,easy,nice
%O A008965 1,2
%A A008965 _Paul Zimmermann_