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

1, 2, 5, 16, 51, 170, 585, 2048, 7280, 26214, 95325, 349520, 1290555, 4793490, 17895679, 67108864, 252645135, 954437120, 3616814565, 13743895344, 52357696365, 199911205050, 764877654105, 2932031006720, 11258999068416

Offset: 1

Author

N. J. A. Sloane, Apr 18 2000

Keywords

• nonn
• easy

Comments

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

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

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

Examples

			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 }.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..1000
• F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
• 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

Crossrefs

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

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

Cf. A074406, A074407, A074408, A074409.

Formula

From Seiichi Manyama, Mar 11 2018: (Start)

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.

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

From Andrey Zabolotskiy, Dec 19 2020: (Start)

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

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

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

Extensions

More terms from James Sellers, Apr 19 2000