|
|
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)
|
|
66
|
|
|
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 2n-bead 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 (for n>=1).
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 trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).
Also number of binary irreducible self-reciprocal 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 Varshamov-Tenengolts code VT_1(n).
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
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
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
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
|
|
REFERENCES
|
B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
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.
May, Robert M. "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
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. 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, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
|
|
FORMULA
|
a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.
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
G.f.: 1 + Sum_{k>=1} mu(2*k)*log(1 - 2*x^k)/(2*k). - Ilya Gutkovskiy, Nov 11 2019
|
|
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}] (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* Michael Somos, Dec 20 2014 *)
|
|
PROG
|
(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;
(Python)
from sympy import divisors, mobius
def a(n): return 1 if n<1 else sum(mobius(d)*2**(n//d) for d in divisors(n) if d%2)//(2*n) # Indranil Ghosh, Apr 28 2017
|
|
CROSSREFS
|
Very close to A006788 [Fisher, 1989].
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|