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

Author

Frank Ruskey, Dec 13 1999

Keywords

• nonn
• easy
• nice

Comments

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

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

Examples

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

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

Crossrefs

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

Cf. A027750, A008683.

Cf. A000010.

Programs

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

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 *)

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 */

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)