# Lyndon words over $GF(k)$ with given trace

Here we consider the number $L(n;t)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet consisting of the elements of the field $GF(k)$ that have trace $t$. The trace of a Lyndon word is the sum of its digits over the field $GF(k)$, i.e., $t = a_1 +a_2 + \cdots + a_n$. Below we use $a=\operatorname{root}(x^2+x+1)$ and $b=1+a$.

 (trace) binary ternary 4-ary 5-ary $n$ 0 1 0 1,2 0 1,$a$,$b$ 0 1,2,3,4 1 1 1 1 1 1 1 1 1 2 0 1 1 1 0 2 2 2 3 1 1 2 3 5 5 8 8 4 1 2 6 6 12 16 30 30 5 3 3 16 16 51 51 124 125 6 4 5 38 39 160 170 516 516 7 9 9 104 104 585 585 2232 2232 8 14 16 270 270 2016 2048 9750 9750 9 28 28 726 729 7280 7280 43400 43400 10 48 51 1960 1960 26112 26214 195248 195250 11 93 93 5368 5368 95325 95325 887784 887784 12 165 170 14736 14742 349180 349520 4068740 4068740 13 315 315 40880 40880 1290555 1290555 18780048 18780048 14 576 585 113828 113828 4792320 4793490 87191964 87191964 15 1091 1091 318848 318864 17895679 17895679 16 2032 2048 896670 896670

## Examples

The two ternary Lyndon words of trace 0 and length 3 are $\{021, 012\}$. The five 4-ary Lyndon words of trace $b$ and length 3 are $\{00b, 01a, 0a1, 11b, aab\}$. The two binary Lyndon words of trace 1 and length 4 are $\{0001, 0111\}$.