|
|
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, 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, 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: A039880 A240452 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
|
|
|
|