A027381 - OEIS

%I #44 Nov 22 2017 16:42:00

%S 1,9,36,240,1620,11808,88440,683280,5380020,43046640,348672528,

%T 2852823600,23535749880,195528140640,1634056262280,13726075468992,

%U 115813759112820,981010688215680,8338590828280440,71097458824894320

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

%C Number of aperiodic necklaces with n beads of 9 colors. - _Herbert Kociemba_, Nov 25 2016

%D E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.

%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

%H Seiichi Manyama, <a href="/A027381/b027381.txt">Table of n, a(n) for n = 0..1051</a> (terms 0..200 from T. D. Noe)

%H A. Pakapongpun, T. Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ward/ward17.html">Functorial Orbit Counting</a>, JIS 12 (2009) 09.2.4, example 3.

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

%H G. Viennot, <a href="http://dx.doi.org/10.1007/BFb0067950">Algèbres de Lie Libres et Monoïdes Libres</a>, Lecture Notes in Mathematics 691, Springer Verlag 1978.

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

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

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

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

%t 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 *)

%t 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 *)

%o (PARI) a(n) = if(n, sumdiv(n, d, moebius(d)*9^(n/d))/n, 1) \\ _Altug Alkan_, Dec 01 2015

%Y Column 9 of A074650.

%Y Cf. A001037.

%K nonn

%O 0,2

%A _N. J. A. Sloane_