A053548 Number of ternary Lyndon words of length n with trace 0 and subtrace 0 over GF(3).

1, 0, 0, 2, 4, 9, 32, 90, 240, 654, 1804, 4950, 13664, 37944, 106272, 298890, 843796, 2390595, 6796160, 19370696, 55345680, 158489298, 454803100, 1307556162, 3765741324, 10862667648, 31381058880, 90780903460, 262951527460

Offset

1,4

Comments

Trace is sum of digits, subtrace is sum of products of pairs of digits. [3|n] above is "Iversonian convention", 1 if 3|n, 0 otherwise.

Links

Table of n, a(n) for n=1..29.

F. Ruskey, Ternary Lyndon words with given trace and subtrace over GF(3)

Formula

a(n) = (1/n) * Sum_{d divides n, d==1, 2(3)} mu(d) * (M(n/d, 0, 0)-[3*d divides n] * 3^{n/(3*d)}), where M(n, t, s) = Sum_{i+j+k=n, j=t(3), k=s(3)} n!/(i!*j!*k!). [Corrected by Sean A. Irvine, Dec 27 2021]

Example

a(4) = 2 = |{ 0111, 0222 }|

Crossrefs

Cf. A053560, A053561, A053562, A053563, A053564.

Sequence in context: A243789 A214935 A092329 * A054119 A259490 A274758

Adjacent sequences: A053545 A053546 A053547 * A053549 A053550 A053551

Keyword

nonn

Author

Frank Ruskey, Jan 16 2000

Status

approved