

A000048


Number of nbead 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)


43



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, 954437120, 1857283155
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Also 2nbead balanced binary necklaces of fundamental period 2n that are equivalent to their complements.
Also binary Lyndon words of length n with an odd number of 1's.
Also number of binary irreducible polynomials of degree n having trace 1.
Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace1 condition, as the reciprocal of an irreducible polynomial is again irreducible).
Also number of binary irreducible selfreciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.
Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of VarshamovTenengolts code VT_1(n).
Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasiminimal negative circuit of size nq where q is odd and which is updated in parallel.  Mathilde Noual (mathilde.noual(AT)enslyon.fr), Mar 03 2009
Also the number of 3elements orbits of the symmetric group S3 action on irreducible polynomials of degree 2n, n>1, over GF(2).  Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univrouen.fr), Oct 04 2009


REFERENCES

J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits", preprint (2009) [From Mathilde Noual (mathilde.noual(AT)enslyon.fr), Mar 03 2009]
B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249252.
H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2  lambda, pp. 7392 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), 459467.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On singledeletioncorrecting codes, in Codes and Designs (Columbus, OH, 2000), 273291, 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).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt, Matters Computational (The Fxtbook), p.408 and p.848.
L. Carlitz, A theorem of Dickson on irreducible polynomials, Proc. Amer. Math. Soc. 3, (1952). 693700.
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657665.
R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887896.
A. A. Kulkarni, N. Kiyavash and R. Sreenivas, On the VarshamovTenengolts Construction on Binary Strings, 2013.
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), 2544; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187206.
H. Meyn and W. Götz, Selfreciprocal polynomials over finite fields
R. Pries and C. Weir, The EkedahlOort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261, 2013
F. Ruskey, Number of qary Lyndon words with given trace mod q
F. Ruskey, Number of Lyndon words of given trace
N. J. A. Sloane, On singledeletioncorrecting codes
P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971
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

a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.


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;


MATHEMATICA

a[n_] := Total[ MoebiusMu[#]*2^(n/#)& /@ Select[ Divisors[n], OddQ]]/(2n); a[0] = 1; Table[a[n], {n, 0, 35}] (* JeanFrançois Alcover, Jul 21 2011 *)


PROG

(PARI) A000048(n) = sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ Michael B. Porter, Nov 09 2009
(PARI) L(n, k) = sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;
vector(55, n, a(n)) \\ Joerg Arndt, Jun 28 2012


CROSSREFS

Like A000013, but primitive necklaces. Half of A064355.
Equals A042981 + A042982. Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076, A008683.
Cf. A001037.  Mathilde Noual (mathilde.noual(AT)enslyon.fr), Mar 03 2009
Sequence in context: A143961 A128023 A056303 * A074099 A006788 A054650
Adjacent sequences: A000045 A000046 A000047 * A000049 A000050 A000051


KEYWORD

nonn,core,easy,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Frank Ruskey, Dec 13 1999


STATUS

approved



