|
Search: id:A000029
|
|
|
| A000029 |
|
Number of necklaces with n beads of 2 colors, allowing turning over.
(Formerly M0563 N0202)
|
|
+0
26
|
|
| 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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
REFERENCES
|
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
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.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
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
H. Bottomley, Illustration of initial terms
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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
|
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]]
|
|
PROGRAM
|
(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.
Sequence in context: A068597 A094372 A039880 this_sequence A155051 A018137 A084239
Adjacent sequences: A000026 A000027 A000028 this_sequence A000030 A000031 A000032
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from Christian G. Bower (bowerc(AT)usa.net)
|
|
|
Search completed in 0.002 seconds
|
