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

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

%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 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, 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, 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 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

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

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

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

%Y Row sums of triangle in A052307.

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

%Y Cf. second column of A081720. - _Wolfdieter Lang_, Jun 03 2012 (edited by _Jon E. Schoenfield_, Mar 23 2014 at the suggestion of _Michel Marcus_)

%K nonn,easy,nice,core

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_