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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000029 Number of necklaces with n beads of 2 colors, allowing turning over.
(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

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, 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, 2012. - From N. J. A. Sloane, Jun 10 2012

S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352, 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: A094372 A039880 A240452 * 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.

Content is available under The OEIS End-User License Agreement .

Last modified April 21 02:07 EDT 2014. Contains 240824 sequences.