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

 

Logo


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

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.

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

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.

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

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)

CROSSREFS

Row sums of triangle in A052307.

Cf. A001371 (primitive necklaces), A000031 (if cannot turn necklace over), A000011, A000013.

Cf. second column of A081720. - Wolfdieter Lang, Jun 03 2012 (edited by Jon E. Schoenfield, Mar 23 2014 at the suggestion of Michel Marcus)

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 18:14 EDT 2016. Contains 274268 sequences.