A027377 Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras.

1, 4, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220, 19172790, 71582716, 268431360, 1010580540, 3817733920, 14467258260, 54975528948, 209430785460, 799644629550, 3059510616420

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Apart from initial terms, exponents in expansion of A065419 as a product zeta(n)^(-a(n)).

Number of aperiodic necklaces with n beads of 4 colors. - Herbert Kociemba, Nov 25 2016

References

• E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
• M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1666 (terms 0..200 from T. D. Noe)
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
• A. Pakapongpun and T. Ward, Functorial Orbit counting, JIS 12 (2009) 09.2.4, example 3.
• Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
• G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
• Index entries for sequences related to Lyndon words

Crossrefs

Cf. A001037, A027376, A054719, A054660, A054661.

Column k=4 of A074650.

Programs

Maple

A027377 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*4^(n/d); od; RETURN(s/n); fi; end;

Mathematica

a[n_] := Sum[MoebiusMu[d]*4^(n/d), {d, Divisors[n]}] / n; a[0] = 1; Table[a[n], {n, 0, 23}](* Jean-François Alcover, Nov 29 2011 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,4],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

PARI

a(n)=if(n,sumdiv(n,d,moebius(d)<<(2*n/d))/n,1) \\ Charles R Greathouse IV, Nov 29 2011

Formula

a(n) = Sum_{d|n} mu(d)*4^(n/d)/n.

G.f.: k=4, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

a(n) = A054661(n) + 3 * A054660(n). - Andrey Zabolotskiy, Dec 17 2020

a(n) = 2 * (A054664(n) + A054660(n)). - Andrey Zabolotskiy, Dec 19 2020

a(n) = A054719(n)/n, n>0. - R. J. Mathar, Dec 16 2024