A051841 Number of binary Lyndon words with an even number of 1's.

1, 0, 1, 1, 3, 4, 9, 14, 28, 48, 93, 165, 315, 576, 1091, 2032, 3855, 7252, 13797, 26163, 49929, 95232, 182361, 349350, 671088, 1290240, 2485504, 4792905, 9256395, 17894588, 34636833, 67106816, 130150493, 252641280, 490853403, 954429840, 1857283155, 3616800768, 7048151355, 13743869130, 26817356775

Offset

1,5

Comments

Also number of trace 0 irreducible polynomials over GF(2).

Also number of trace 0 Lyndon words over GF(2).

References

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

Links

T. D. Noe, Table of n, a(n) for n = 1..300

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

F. Ruskey, Number of Lyndon words over GF(q) with given trace

Index entries for sequences related to Lyndon words

Formula

a(n) = 1/(2*n)*Sum_{d|n} gcd(d,2)*mu(d)*2^(n/d).

a(n) ~ 2^(n-1) / n. - Vaclav Kotesovec, May 31 2019

From Richard L. Ollerton, May 10 2021: (Start)

a(n) = 1/(2*n)*Sum_{k=1..n} gcd(gcd(n,k),2)*mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).

a(n) = (1/n)*Sum_{k=1..n} gcd(n/gcd(n,k),2)*mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)

Example

a(5) = 3 = |{ 00011, 00101, 01111 }|.

Mathematica

a[n_] := Sum[GCD[d, 2]*MoebiusMu[d]*2^(n/d), {d, Divisors[n]}]/(2n);
Table[a[n], {n, 1, 32}]
(* Jean-François Alcover, May 14 2012, from formula *)

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==0, L(n, k), 0 ) ) / n;
vector(33, n, a(n))
/* Joerg Arndt, Jun 28 2012 */
(Haskell)
a051841 n = (sum $ zipWith (\u v -> gcd 2 u * a008683 u * 2 ^ v)
             ds $ reverse ds) `div` (2 * n) where ds = a027750_row n
-- Reinhard Zumkeller, Mar 17 2013

Crossrefs

Same as A001037 - A000048. Same as A042980 + A042979.

Cf. A027750, A008683.

Cf. A000010.

Sequence in context: A002823 A109509 A006053 * A096081 A054162 A174783

Adjacent sequences: A051838 A051839 A051840 * A051842 A051843 A051844

Keyword

nonn,easy,nice

Author

Frank Ruskey, Dec 13 1999

Status

approved