A046211 Number of ternary Lyndon words whose digits sum to 1 (or 2) mod 3; number of trace 1 (or 2) monic irreducible polynomials over GF(3).
1, 1, 3, 6, 16, 39, 104, 270, 729, 1960, 5368, 14742, 40880, 113828, 318864, 896670, 2532160, 7174089, 20390552, 58112088, 166037352, 475467916, 1364393896, 3922625070, 11297181456, 32588003000, 94143178827, 272342710380, 788854912240, 2287679086056, 6641649422408, 19302293185470
Offset: 1
Keywords
Examples
a(4)= 6 = |{ 0001, 0022, 0112, 0121, 0211, 1222 }|.
Links
- G. C. Greubel, Table of n, a(n) for n = 1..2000
- F. Ruskey, Number of q-ary Lyndon words with given trace mod q
- F. Ruskey, Number of monic irreducible polynomials over GF(q) with given trace
- F. Ruskey, Number of Lyndon words over GF(q) with given trace
- Index entries for sequences related to Lyndon words
Programs
-
Mathematica
a[n_] := 1/(3n) DivisorSum[n, If[GCD[#, 3] == 1, MoebiusMu[#]*3^(n/#), 0] &]; Array[a, 32] (* Jean-François Alcover, Dec 07 2015 *)
-
PARI
a(n) = 1/(3*n) * sumdiv(n, d, if(gcd(d, 3)==1, moebius(d)*3^(n/d), 0 ) ); /* Joerg Arndt, Aug 17 2012 */
Formula
a(n) = 1/(3*n) * Sum_{d divides n, gcd(d, 3)=1} mu(d) * 3^{n/d}.
a(n) ~ 3^(n-1) / n. - Vaclav Kotesovec, Apr 18 2016
Comments