%I #46 Jan 16 2024 17:32:00

%S 1,2,5,16,51,170,585,2048,7280,26214,95325,349520,1290555,4793490,

%T 17895679,67108864,252645135,954437120,3616814565,13743895344,

%U 52357696365,199911205050,764877654105,2932031006720,11258999068416

%N Number of monic irreducible polynomials over GF(4) of degree n with fixed nonzero trace.

%C Also number of Lyndon words of length n with trace 1 over GF(4).

%C Let x = RootOf( z^2+z+1 ) and y = 1+x. Also number of Lyndon words of length n with trace x over GF(4). Also number of Lyndon words of length n with trace y over GF(4).

%C Also number of 4-ary Lyndon words (i.e., Lyndon words over Z_4) of length n with trace 1 (mod 4). Also the same with trace 3 (mod 4). - _Andrey Zabolotskiy_, Dec 19 2020

%H Seiichi Manyama, <a href="/A054660/b054660.txt">Table of n, a(n) for n = 1..1000</a>

%H F. Ruskey, <a href="http://combos.org/Tpoly">Number of monic irreducible polynomials over GF(q) with given trace</a>

%H F. Ruskey, <a href="http://combos.org/TlyndonZk">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>

%F From _Seiichi Manyama_, Mar 11 2018: (Start)

%F a(n) = A000048(2*n) = (1/(4*n)) * Sum_{odd d divides n} mu(d)*4^(n/d), where mu is the Möbius function A008683.

%F a(n+1) = A300628(n,n) for n >= 0. (End)

%F From _Andrey Zabolotskiy_, Dec 19 2020: (Start)

%F a(n) = A074033(n) + A074034(n) + 2 * A074035(n).

%F a(n) = A074448(n) + A074449(n) + 2 * A074450(n).

%F a(n) = A074406(n) + A074407(n) + A074408(n) + A074409(n). (End)

%e a(3; y)=5 since the five Lyndon words over GF(4) of trace y and length 3 are { 00y, 01x, 0x1, 11y, xxy }; the five Lyndon words over Z_4 of trace 1 (mod 4) and length 3 are { 001, 023, 032, 113, 122 }.

%Y Cf. A000048, A051841, A046211, A046209, A054661, etc.

%Y Cf. A008683, A054661, A027377, A300628, A074033, A074034, A074035, A074448, A074449, A074450.

%Y Cf. A074406, A074407, A074408, A074409.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_, Apr 18 2000

%E More terms from _James A. Sellers_, Apr 19 2000