A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).

1, 2, 3, 4, 6, 8, 13, 18, 30, 46, 78, 126, 224, 380, 687, 1224, 2250, 4112, 7685, 14310, 27012, 50964, 96909, 184410, 352698, 675188, 1296858, 2493726, 4806078, 9272780, 17920860, 34669602, 67159050, 130216124, 252745368, 490984488, 954637558, 1857545300

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• core

Comments

"Necklaces with turning over allowed" are usually called bracelets. - Joerg Arndt, Jun 10 2016

Examples

			For n=2, the three bracelets are AA, AB, and BB. For n=3, the four bracelets are AAA, AAB, ABB, and BBB. - _Robert A. Russell_, Sep 24 2018
		

References

• J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.
• Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..300
• Hoda Abbasizanjani and Oliver Kullmann, Classification of minimally unsatisfiable 2-CNFs, arXiv:2003.03639 [cs.DM], 2020.
• Joerg Arndt, Matters Computational (The Fxtbook), p. 151
• Henry Bottomley, Illustration of initial terms
• Emanuele Brugnoli, Enumerating the Walecki-Type Hamiltonian Cycle Systems, Journal of Combinatorial Designs, Volume 25, Issue 11, November 2017, pp. 481-493.
• P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
• S. N. Ethier and J. Lee, Parrondo games with spatial dependence, arXiv preprint arXiv:1202.2609 [math.PR], 2012. - From _N. J. A. Sloane_, Jun 10 2012
• S. N. Ethier and J. Lee, Parrondo games with spatial dependence II, Fluctuation and Noise Letters 11 (4) (2012), 1250030.
• S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013.
• S. N. Ethier, Counting toroidal binary arrays, Journal of Integer Sequences 16 (2013), Article 13.4.7.
• N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• Jurij Kovič, Regular polygonal systems, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 157-171.
• Jia Liu, L. Lalouat, E. Drouard, and R. Orobtchouk, Binary coded patterns for photon control using necklace problem concept, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Zhe Sun, T. Suenaga, P. Sarkar, S. Sato, M. Kotani, and H. Isobe, Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes, Proc. Nat. Acad. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113.
• James Tilley, Stan Wagon, and Eric Weisstein, A Catalog of Facially Complete Graphs, arXiv:2409.11249 [math.CO], 2024. See p. 11.
• A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012. - From _N. J. A. Sloane_, Dec 31 2012
• Eric Weisstein's World of Mathematics, Necklace
• Eric Weisstein's World of Mathematics, e
• Index entries for "core" sequences
• Index entries for sequences related to bracelets
• Index entries for sequences related to necklaces

Crossrefs

Row sums of triangle in A052307, second column of A081720, column 2 of A051137.

Cf. A000011, A000013, A000031 (turning over not allowed), A001371 (primitive necklaces), A059076, A164090.

Cf. A000031, A051137.

Programs

Maple

with(numtheory): A000029 := proc(n) local d,s; if n = 0 then return 1 else if n mod 2 = 1 then s := 2^((n-1)/2) else s := 2^(n/2-2)+2^(n/2-1) fi; for d in divisors(n) do s := s+phi(d)*2^(n/d)/(2*n) od; return s; fi end:

Mathematica

a[0] := 1; a[n_] := Fold[#1 + EulerPhi[#2]2^(n/#2)/(2n) &, If[OddQ[n], 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)], Divisors[n]]
mx=40;CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n,{n,mx}]+(1+x)^2/(1-2*x^2))/2,{x,0,mx}],x] (* Herbert Kociemba, Nov 02 2016 *)
a[0] = 1; a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n); Array[a, 36, 0] (* Jean-François Alcover, Nov 05 2017 *)

PARI

a(n)=if(n<1,!n,(n%2+3)/4*2^(n\2)+sumdiv(n,d,eulerphi(n/d)*2^d)/2/n)

Python

from sympy import divisors, totient
def a(n):
    return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

Formula

a(n) = Sum_{d divides n} phi(d)*2^(n/d)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.

G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n + (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016

Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - Robert A. Russell, Sep 24 2018

From Richard L. Ollerton, May 04 2021: (Start)

a(0) = 1; a(n) = Sum_{k=1..n} 2^gcd(n,k)/(2*n) + either 2^((n - 1)/2) if n odd or 2^(n/2 - 1) + 2^(n/2 - 2) if n even.

a(0) = 1; a(n) = A000031(n)/2 + (2^floor((n+1)/2) + 2^ceiling((n+1)/2))/4. See A051137. (End)

Extensions

More terms from Christian G. Bower