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