Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #14 Aug 13 2023 02:47:13
%S 1,9,45,489,4941,47241,443001,4099689,37666701,344373849,3138111873,
%T 28528236009,258893786601,2346337687689,21242736192681,
%U 192165056625657,1737206429739021,15696171011450889,141756044468718681,1279754258848097769,11549782186278421905,104208561077631046089
%N a(0) = 1, a(1) = 9; for n >= 2 a(n) is the number of degree-n monic reducible polynomials over GF(9), i.e., a(n) = 9^n - A027381(n).
%C Dimensions of homogeneous subspaces of shuffle algebra over 9-letter alphabet (see A058766 for 2-letter case).
%D M. Lothaire, Combinatorics on words, Cambridge mathematical library, 1983, p. 126 (definition of shuffle algebra).
%t a[n_] := 9^n - DivisorSum[n, MoebiusMu[n/#] * 9^# &] / n; a[0] = 1; a[1] = 9; Array[a, 22, 0] (* _Amiram Eldar_, Aug 13 2023 *)
%o (PARI) a(n) = if (n<=1, 9^n, 9^n - sumdiv(n, d, moebius(d)*9^(n/d))/n); \\ _Michel Marcus_, Oct 30 2017
%Y Cf. A001019, A027381, A058766.
%K nonn
%O 0,2
%A Claude Lenormand (claude.lenormand(AT)free.fr), Jan 04 2001
%E Better description from Sharon Sela (sharonsela(AT)hotmail.com), Feb 19 2002
%E More terms from _Michel Marcus_, Oct 30 2017