login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051841 Number of binary Lyndon words with an even number of 1's. 15

%I

%S 1,0,1,1,3,4,9,14,28,48,93,165,315,576,1091,2032,3855,7252,13797,

%T 26163,49929,95232,182361,349350,671088,1290240,2485504,4792905,

%U 9256395,17894588,34636833,67106816,130150493,252641280,490853403,954429840,1857283155,3616800768,7048151355,13743869130,26817356775

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

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

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

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

%H T. D. Noe, <a href="/A051841/b051841.txt">Table of n, a(n) for n = 1..300</a>

%H F. Ruskey, <a href="http://combos.org/TSlyndon">Number of q-ary Lyndon words with given trace mod q</a>

%H F. Ruskey, <a href="http://combos.org/TlyndonFk">Number of Lyndon words over GF(q) with given trace</a>

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

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

%F a(n) ~ 2^(n-1) / n. - _Vaclav Kotesovec_, May 31 2019

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

%t a[n_] := Sum[GCD[d, 2]*MoebiusMu[d]*2^(n/d), {d, Divisors[n]}]/(2n);

%t Table[a[n], {n, 1, 32}]

%t (* _Jean-Fran├žois Alcover_, May 14 2012, from formula *)

%o (PARI)

%o 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==0, L(n, k), 0 ) ) / n;

%o vector(33,n,a(n))

%o /* _Joerg Arndt_, Jun 28 2012 */

%o (Haskell)

%o a051841 n = (sum $ zipWith (\u v -> gcd 2 u * a008683 u * 2 ^ v)

%o ds $ reverse ds) `div` (2 * n) where ds = a027750_row n

%o -- _Reinhard Zumkeller_, Mar 17 2013

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

%Y Cf. A027750, A008683.

%K nonn,easy,nice

%O 1,5

%A _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 September 21 01:52 EDT 2020. Contains 337266 sequences. (Running on oeis4.)