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\}$.
Enumeration (OEIS)