Logo

Greetings from The On-Line Encyclopedia of Integer Sequences!

Hints

Search: id:A000048
Displaying 1-1 of 1 results found. page 1
     Format: long | short | internal | text      Sort: relevance | references | number      Highlight: on | off
A000048 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.
(Formerly M0711 N0262)
+0
35
1, 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403 (list; graph; listen)
OFFSET

0,5

COMMENT

Also 2n-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements; binary Lyndon words of length n with an odd number of 1's; number of binary irreducible polynomials of degree n having trace 1.

Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of Varshamov-Tenengolts code VT_1(n).

The trace of a polynomial of degree n is the coefficient of x^(n-1); the subtrace is the coefficient of x^(n-2).

Also number of binary Lyndon words with trace 1 over GF(2).

Number of self-reciprocal polynomials of degree 2n over GF(2).

REFERENCES

L. Carlitz, A theorem of Dickson on irreducible polynomials. Proc. Amer. Math. Soc. 3, (1952). 693-700.

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.

B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.

R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896.

H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2 - lambda, pp. 73-92 of G. Ikegami, Editor, Dynamical Systems and Nonlinear Oscillations, Vol. 1, World Scientific, 1986.

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

N. Metropolis, M. L. Stein and P. R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.

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.

LINKS

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

Joerg Arndt, Fxtbook

H. Meyn and W. G\"otz, Self-reciprocal polynomials over finite fields

F. Ruskey, Number of q-ary Lyndon words with given trace mod q

F. Ruskey, Number of Lyndon words of given trace

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

J.-Y. Thibon, The cycle enumerator of unimodal permutations.

Index entries for "core" sequences

Index entries for sequences related to Lyndon words

Index entries for sequences related to subset sums modulo m

FORMULA

(Sum_{odd d divides n } mu(d)*2^(n/d)) / (2n).

EXAMPLE

a(5) = 3 corresponding to the necklaces 00001, 00111, 01011; a(6) = 5 from 000001, 000011, 000101, 000111, 001011.

MAPLE

with(numtheory); A000048 := proc(n) local d, t1; if n = 0 then RETURN(1) else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+mobius(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;

CROSSREFS

Like A000013, but primitive necklaces. Half of A064355.

Equals A042981 + A042982. Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076.

Sequence in context: A114834 A128023 A056303 this_sequence A074099 A006788 A054650

Adjacent sequences: A000045 A000046 A000047 this_sequence A000049 A000050 A000051

KEYWORD

nonn,core,easy,nice

AUTHOR

njas

EXTENSIONS

Additional comments from Frank Ruskey (fruskey(AT)cs.uvic.ca), Dec 13 1999

page 1

Search completed in 0.003 seconds

Lookup | Welcome | Find friends | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
More pages | Superseeker | Maintained by N. J. A. Sloane (njas@research.att.com)

Last modified July 24 12:00 EDT 2008. Contains 142294 sequences.


AT&T Labs Research