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

1, 9, 36, 240, 1620, 11808, 88440, 683280, 5380020, 43046640, 348672528, 2852823600, 23535749880, 195528140640, 1634056262280, 13726075468992, 115813759112820, 981010688215680, 8338590828280440, 71097458824894320

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

Examples

			G.f. = 1 + 9*x + 36*x^2 + 240*x^3 + 1620*x^4 + 11808*x^5 + 88440*x^6 + ...
		

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..1051 (terms 0..200 from T. D. Noe)
• A. Pakapongpun, 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

Column 9 of A074650.

Cf. A001037.

Programs

Mathematica

f[n_] := (1/n)*Sum[ MoebiusMu[d]*9^(n/d), {d, Divisors[n]}]; f[0] = 1; Array[f, 20, 0] (* Robert G. Wilson v, Jul 28 2014 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,9],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

PARI

a(n) = if(n, sumdiv(n, d, moebius(d)*9^(n/d))/n, 1) \\ Altug Alkan, Dec 01 2015

Formula

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

a(n) = Sum_{d|n} mu(d)*9^(n/d)/n for n > 0. - Andrew Howroyd, Oct 13 2017