login
The OEIS is supported by the many generous donors 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. 181

%I #106 Mar 09 2024 12:32:42

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

%C Inverse Mobius transform of A059966. - _Jianing Song_, Nov 13 2021

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

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

%F From _Jianing Song_, Nov 13 2021: (Start)

%F 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 Dirichlet g.f.: zeta(s) * (f(s+1)/zeta(s+1) - 1), where f(s) = Sum_{n>=1} 2^n/n^s. (End)

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

%o (Python)

%o from sympy import totient, divisors

%o 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 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)