A046209 Number of ternary Lyndon words whose digits sum to 0 mod 3; also number of trace 0 irreducible polynomials over GF(3).

1, 1, 2, 6, 16, 38, 104, 270, 726, 1960, 5368, 14736, 40880, 113828, 318848, 896670, 2532160, 7174050, 20390552, 58112088, 166037248, 475467916, 1364393896, 3922624800, 11297181456, 32588003000, 94143178098, 272342710380, 788854912240, 2287679084096, 6641649422408, 19302293185470

Offset: 1

Author

Frank Ruskey, Dec 13 1999

Keywords

• nonn

Comments

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

Examples

			a(4) = 6 = |{ 0012, 0021, 0111, 0102, 0222, 1122 }|.
		

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

Crossrefs

Cf. A046211.

Programs

Mathematica

a[n_] := 1/(3n) DivisorSum[n, GCD[#, 3]*MoebiusMu[#]*3^(n/#)&]; Array[a, 32] (* Jean-François Alcover, Dec 06 2015, adapted from PARI *)

PARI

a(n) = 1/(3*n) * sumdiv(n, d, gcd(d, 3)*moebius(d)*3^(n/d) ); /* Joerg Arndt, Aug 17 2012 */

Formula

a(n) = 1/(3*n) * sum(d divides n, gcd(d, 3)*mu(d)*3^(n/d) ).

a(n) = A053548(n) + A053560(n) + A053561(n). - R. J. Mathar, Oct 21 2021