|
%I #44 May 10 2021 11:32:08
%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) = 1/(2*n)*Sum_{d|n} gcd(d,2)*mu(d)*2^(n/d).
%F a(n) ~ 2^(n-1) / n. - _Vaclav Kotesovec_, May 31 2019
%F From _Richard L. Ollerton_, May 10 2021: (Start)
%F 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)).
%F 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)
%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.
%Y Cf. A000010.
%K nonn,easy,nice
%O 1,5
%A _Frank Ruskey_, Dec 13 1999
|
