This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000029 Number of necklaces with n beads of 2 colors, allowing turning over (these are also called bracelets).
(Formerly M0563 N0202)

%I M0563 N0202

%S 1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,1224,2250,4112,7685,14310,

%T 27012,50964,96909,184410,352698,675188,1296858,2493726,4806078,

%U 9272780,17920860,34669602,67159050,130216124,252745368,490984488

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

%C "Necklaces with turning over allowed" are usually called bracelets. - _Joerg Arndt_, Jun 10 2016

%D J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.

%D Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

%H N. J. A. Sloane, <a href="/A000029/b000029.txt">Table of n, a(n) for n = 0..300</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 151

%H H. Bottomley, <a href="/A000029/a000029.gif">Illustration of initial terms</a>

%H Emanuele Brugnoli, <a href="https://dx.doi.org/10.1002/jcd.21558">Enumerating the Walecki-Type Hamiltonian Cycle Systems</a>, Journal of Combinatorial Designs, Volume 25, Issue 11, November 2017, pp. 481-493.

%H P. J. Cameron, <a href="http://www.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 S. N. Ethier and J. Lee, <a href="http://arxiv.org/abs/1202.2609">Parrondo games with spatial dependence</a>, arXiv preprint arXiv:1202.2609 [math.PR], 2012. - From _N. J. A. Sloane_, Jun 10 2012

%H S. N. Ethier, <a href="http://arxiv.org/abs/1301.2352">Counting toroidal binary arrays</a>, arXiv preprint arXiv:1301.2352 [math.CO], 2013.

%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.

%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.

%H Jia Liu, L. Lalouat, E. Drouard, R. Orobtchouk, <a href="https://doi.org/10.1364/OE.24.001133">Binary coded patterns for photon control using necklace problem concept</a>, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).

%H F. Ruskey, <a href="https://web.archive.org/web/20170113110237/http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

%H Zhe Sun, T. Suenaga, P. Sarkar, S. Sato, M. Kotani, H. Isobe, <a href="https://doi.org/10.1073/pnas.1606530113">Stereoisomerism, crystal structures, and dynamics of belt-shaped cyclonaphthylenes</a>, Proc. Nat. Acad. Sci. USA, vol. 113 no. 29, pp. 8109-8114, doi: 10.1073/pnas.1606530113.

%H A. M. Uludag, A. Zeytin and M. Durmus, <a href="http://math.gsu.edu.tr/uludag/CHARKSANDDESSINS.pdf">Binary Quadratic Forms as Dessins</a>, 2012. - From _N. J. A. Sloane_, Dec 31 2012

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Necklace.html">Necklace</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/e.html">e</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

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

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

%F Equals (A000031 + A164090) / 2 = A000031 - A059076 = A059076 + A164090. - _Robert A. Russell_, Sep 24 2018

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

%p 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:

%t 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]]

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

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

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

%o (Python)

%o from sympy import divisors, totient

%o def a(n): return 1 if n<1 else (n%2 + 3)/4*2**int(n/2) + sum([totient(n/d)*2**d for d in divisors(n)])/(2*n)

%o print [a(n) for n in xrange(51)] # _Indranil Ghosh_, Apr 23 2017

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

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

%K nonn,easy,nice,core,changed

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 23:05 EST 2019. Contains 319282 sequences. (Running on oeis4.)