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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000031 Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.
(Formerly M0564 N0203)
76
1, 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580, 18512792, 35792568, 69273668, 134219796, 260301176, 505294128, 981706832 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).

In music, a(n) is the number of distinct classes of scales and chords in an n-note equal-tempered tuning system. [Paul Cantrell, Dec 28 2011]

REFERENCES

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.

H. Fredricksen, The lexicographically least de Bruijn cycle, J. Combin. Theory, 9 (1970) 1-5.

Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, Pages 181-188

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.

Lempel, Abraham. On extremal factors of the de Bruijn graph. J. Combinatorial Theory Ser. B 11 1971 17--27. MR0276126 (43 #1874)

R. M. May, Simple mathematical models with very complicated dynamics, Nature, 261 (Jun 10, 1976), 459-467.

Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.

Mykkeltveit, Johannes. A proof of Golomb's conjecture for the de Bruijn graph. J. Combinatorial Theory Ser. B 13 (1972), 40--45.MR0323629 (48 #1985)

J. A. Siehler, The Finite Lamplighter Groups: A Guided Tour, College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 203-211. - From N. J. A. Sloane, Oct 05 2012

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, http://math.gsu.edu.tr/uludag/CHARKSANDDESSINS.pdf, 2012. - From N. J. A. Sloane, Dec 31 2012

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

Joerg Arndt, Fxtbook, p. 151, pp. 379-383

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.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 18, 64

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 2

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 130

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

N. J. A. Sloane, On single-deletion-correcting codes

Eric Weisstein's World of Mathematics, Necklace

Wolfram Research, Number of necklaces

Index entries for "core" sequences

Index entries for sequences related to necklaces

FORMULA

a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d), where phi is A000010.

Warning: easily confused with A001037 which has a similar formula.

EXAMPLE

For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.

The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111... }.

MAPLE

with(numtheory); A000031 := proc(n) local d, s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq(A000031(n), n=0..50) ];

MATHEMATICA

a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n

a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n

Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n, 0, 30}] (* Geoffrey Critzer, Mar 06 2011*)

PROG

(PARI) {A000031(n)=if(n==0, 1, sumdiv(n, d, eulerphi(d)*2^(n/d))/n)}. - Randall L. Rathbun, Jan 11 2002

(Haskell)

a000031 0 = 1

a000031 n = (`div` n) $ sum $

   zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)

   where divs = a027750_row n

-- Reinhard Zumkeller, Mar 21 2013

CROSSREFS

Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.

Rows sums of triangle in A047996.

Dividing by 2 gives A053634.

A008965(n) = a(n) - 1 allowing different offsets.

Cf. A008965, A053635, A052823.

Sequence in context: A084239 A219186 A049708 * A111023 A008324 A084074

Adjacent sequences:  A000028 A000029 A000030 * A000032 A000033 A000034

KEYWORD

nonn,easy,nice,core

AUTHOR

N. J. A. Sloane.

EXTENSIONS

There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).

Corrected Mathematica code by Ben Branman, Jan 08 2011

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 July 30 19:06 EDT 2014. Contains 245074 sequences.