login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(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)
36
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..300

Joerg Arndt, Matters Computational (The Fxtbook), p. 151

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

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, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013.

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.

Jia Liu, L. Lalouat, E. Drouard, R. Orobtchouk, Binary coded patterns for photon control using necklace problem concept, Optics Express Vol. 24, Issue 2, pp. 1133-1142 (2016).

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

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

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

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

EXAMPLE

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

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

PROG

(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 (n%2 + 3)/4*2**int(n/2) + sum([totient(n/d)*2**d for d in divisors(n)])/(2*n)

print [a(n) for n in xrange(51)] # Indranil Ghosh, Apr 23 2017

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.

Sequence in context: A240452 A263359 A246905 * A155051 A018137 A084239

Adjacent sequences:  A000026 A000027 A000028 * A000030 A000031 A000032

KEYWORD

nonn,easy,nice,core

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Christian G. Bower

STATUS

approved

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 December 13 16:06 EST 2018. Contains 318086 sequences. (Running on oeis4.)