This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)

%I M0711 N0262

%S 1,1,1,1,2,3,5,9,16,28,51,93,170,315,585,1091,2048,3855,7280,13797,

%T 26214,49929,95325,182361,349520,671088,1290555,2485504,4793490,

%U 9256395,17895679,34636833,67108864,130150493,252645135,490853403,954437120,1857283155

%N 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.

%C Also 2n-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements.

%C Also binary Lyndon words of length n with an odd number of 1's (for n>=1).

%C Also number of binary irreducible polynomials of degree n having trace 1.

%C Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).

%C Also number of binary irreducible self-reciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.

%C 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).

%C Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasi-minimal negative circuit of size nq where q is odd and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009

%C Also the number of 3-elements 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)univ-rouen.fr), Oct 04 2009

%C Conjecture: Also the number of caliber-n cycles of Zagier-reduced indefinite binary quadratic forms with sum invariant equal to s, where (s-1)/n is an odd integer. - _Barry R. Smith_, Dec 14 2014

%C The Metropolis, Stein, Stein (1973) reference on page 31 Table II lists a(k) for k = 2 to 15 and is actually for sequence A056303 since there a(k) = 0 for k<2. - _Michael Somos_, Dec 20 2014

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

%D 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.

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

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

%H G. C. Greubel, <a href="/A000048/b000048.txt">Table of n, a(n) for n = 0..3320</a> (terms 0..200 from T. D. Noe)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.408 and p.848.

%H L. Carlitz, <a href="http://dx.doi.org/10.1090/S0002-9939-1952-0049940-6">A theorem of Dickson on irreducible polynomials</a>, Proc. Amer. Math. Soc. 3, (1952). 693-700.

%H J. Demongeot, M. Noual and S. Sene, <a href="https://hal.archives-ouvertes.fr/hal-00647877">On the number of attractors of positive and negative threshold Boolean automata circuits</a>, hal-00647877 preprint (2009). [From Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009]

%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.

%H H. L. Fisher, <a href="/A027601/a027601.pdf">Letter to N. J. A. Sloane, Mar 16 1989</a>

%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.

%H R. W. Hall and P. Klingsberg, <a href="http://www.jstor.org/stable/27642087">Asymmetric rhythms and tiling canons</a>, Amer. Math. Monthly, 113 (2006), 887-896.

%H J. E. Iglesias, <a href="https://dx.doi.org/10.1107/S0108767306003126">Enumeration of polytypes MX and MX_2 through the use of the symmetry of the Zhadanov symbol</a>, Acta Cryst. A 62 (3) (2006) 178-194, Table 1.

%H Veronika Irvine, <a href="http://hdl.handle.net/1828/7495">Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns</a>, PhD Dissertation, University of Victoria, 2016.

%H A. A. Kulkarni, N. Kiyavash and R. Sreenivas, <a href="http://www.sc.iitb.ac.in/~ankur/docs/CombinInsightDM_final.pdf">On the Varshamov-Tenengolts Construction on Binary Strings</a>, 2013.

%H R. P. Loh, A. G. Shannon, A. F. Horadam, <a href="/A000969/a000969.pdf">Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients</a>, Preprint, 1980.

%H R. M. May, <a href="http://abel.harvard.edu/archive/118r_spring_05/docs/may.pdf">Simple mathematical models with very complicated dynamics</a>, Nature, 261 (Jun 10, 1976), 459-467.

%H N. Metropolis, M. L. Stein and P. R. Stein, <a href="http://dx.doi.org/10.1016/0097-3165(73)90033-2">On finite limit sets for transformations on the unit interval</a>, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.

%H H. Meyn and W. Götz, <a href="http://www.mat.univie.ac.at/~slc/opapers/s21meyn.html">Self-reciprocal polynomials over finite fields</a>, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.

%H Simon Michalowsky, Bahman Gharesifard, Christian Ebenbauer, <a href="https://arxiv.org/abs/1711.05486">A Lie bracket approximation approach to distributed optimization over directed graphs</a>, arXiv:1711.05486 [math.OC], 2017.

%H R. Pries and C. Weir, <a href="http://arxiv.org/abs/1302.6261">The Ekedahl-Oort type of Jacobians of Hermitian curves</a>, arXiv preprint arXiv:1302.6261 [math.NT], 2013.

%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/neck/lyndon.html">Number of q-ary Lyndon words with given trace mod q</a>

%H F. Ruskey, <a href="http://www.theory.csc.uvic.ca/~cos/inf/trs/lyn/Fq/lyn_tr_Fq.html">Number of Lyndon words of given trace</a>

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/math/0207197">On single-deletion-correcting codes</a>, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>

%H B. R. Smith, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Smith/smith5.html"> Reducing quadratic forms by kneading sequences</a>, Journal of Integer Sequences, 17 (2014), article 14.11.8.

%H P. R. Stein, <a href="/A000048/a000048.pdf">Letter to N. J. A. Sloane, Jun 02 1971</a>

%H J.-Y. Thibon, <a href="http://www.arXiv.org/abs/math.CO/0102051">The cycle enumerator of unimodal permutations</a>, arXiv:math/0102051 [math.CO], 2001.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%H <a href="/index/Su#subsetsums">Index entries for sequences related to subset sums modulo m</a>

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

%F a(n) = A056303(n) for all integer n>=2. - _Michael Somos_, Dec 20 2014

%F Sum_{k dividing m for which m/k is odd} k*a(k) = 2^(m-1). (This explains the observation that the sequence is very close to A006788. Unless m has some nontrivial odd divisors that are small relative to m, the term m*a(m) will dominate the sum. Thus, we see for instance that a(n) = A006788(n) when n has one of the forms 2^m or 2^m*p where p is an odd prime with a(2^m) < p.) - _Barry R. Smith_, Oct 24 2015

%e a(5) = 3 corresponding to the necklaces 00001, 00111, 01011.

%e a(6) = 5 from 000001, 000011, 000101, 000111, 001011.

%p 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;

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

%t a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* _Michael Somos_, Dec 20 2014 *)

%o (PARI) A000048(n) = sumdiv(n,d,(d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ _Michael B. Porter_, Nov 09 2009

%o (PARI) L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );

%o a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;

%o vector(55,n,a(n)) \\ _Joerg Arndt_, Jun 28 2012

%o (Python)

%o from sympy import divisors, mobius

%o def a(n): return 1 if n<1 else sum([mobius(d)*2**(n/d) for d in divisors(n) if d%2 == 1])/(2*n) # _Indranil Ghosh_, Apr 28 2017

%Y Like A000013, but primitive necklaces. Half of A064355.

%Y Equals A042981 + A042982.

%Y Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076, A008683.

%Y Cf. also A001037, A056303.

%Y Very close to A006788 [Fisher, 1989].

%K nonn,core,easy,nice

%O 0,5

%A _N. J. A. Sloane_

%E Additional comments from _Frank Ruskey_, Dec 13 1999

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 15:57 EST 2019. Contains 319364 sequences. (Running on oeis4.)