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,3

Comments

Also number of ternary Lyndon words of trace 1 over GF(3).

Also number of ternary Lyndon words of trace 2 over GF(3).

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

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

Example

a(4)= 6 = |{ 0001, 0022, 0112, 0121, 0211, 1222 }|.

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

Prog

(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 */

Crossrefs

Cf. A008683 (mu), A046209.

Sequence in context: A248091 A168317 A188442 * A239980 A205770 A301959

Adjacent sequences: A046208 A046209 A046210 * A046212 A046213 A046214

Keyword

nonn

Author

Frank Ruskey, Dec 13 1999

Status

approved