Lyndon words over $GF(3)$ with given trace and subtrace
Here we consider the number $L(n;t,s)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet consisting of the elements of the field $GF(3)$ that have trace $t$ and subtrace $s$.
The
trace of a Lyndon word is the sum of its digits over the field, i.e., $t = a_1 + a_2 + \cdots + a_n$.
The
subtrace is the sum of the products of all $n(n-1)/2$ pairs of digits taken over the field, i.e., $s=\sum_{1\leq i\lt j\leq n} a_i a_j$.
Note that $GF(3)=\mathbb{Z}_3$.
|
| (trace,subtrace) |
| $n$
| (0,0)
| (0,1)
| (0,2)
| (1,0)
(2,0)
| (1,1)
(2,1)
| (1,2)
(2,2)
|
| 1 |
1 | 0 | 0
| 1 | 0 | 0
|
|---|
| 2 |
0 | 0 | 1
| 1 | 0 | 0
|
|---|
| 3 |
0 | 0 | 2
| 1 | 1 | 1
|
|---|
| 4 |
2 | 1 | 3
| 2 | 1 | 3
|
|---|
| 5 |
4 | 6 | 6
| 6 | 4 | 6
|
|---|
| 6 |
9 | 14 | 15
| 13 | 13 | 13
|
|---|
| 7 |
32 | 36 | 36
| 32 | 36 | 36
|
|---|
| 8 |
90 | 93 | 87
| 87 | 90 | 93
|
|---|
| 9 |
240 | 252 | 234
| 243 | 243 | 243
|
|---|
| 10 |
654 | 661 | 645
| 654 | 661 | 645
|
|---|
| 11 |
1804 | 1782 | 1782
| 1782 | 1804 | 1782
|
|---|
| 12 |
4950 | 4893 | 4893
| 4914 | 4914 | 4914
|
|---|
| 13 |
13664 | 13608 | 13608
| 13664 | 13608 | 13608
|
|---|
| 14 |
37944 | 37890 | 37994
| 37994 | 37944 | 37890
|
|---|
| 15 |
106272 | 106142 | 106434
| 106288 | 106288 | 106288
|
|---|
| 16 |
298890 | 298755 | 299025
| 298890 | 298755 | 299025
|
|---|
| 17 |
843796 | 844182 | 844182
| 844182 | 843796 | 844182
|
|---|
| 18 |
2390595 | 2391732 | 2391723
| 2391363 | 2391363 | 2391363
|
|---|
| 19 |
6796160 | 6797196 | 6797196
| 6796160 | 6797196 | 6797196
|
|---|
| 20 |
19370696 | 19371684 | 19369708
| 19369708 | 19370696 | 19371684
|
|---|
Examples
The two ternary Lyndon words of trace 0, subtrace 0 and length 4 are $\{0111, 0222\}$.
The three ternary Lyndon words of trace 1, subtrace 2 and length 4 are $\{0112, 0121, 0211\}$.
The six ternary Lyndon words of trace 2, subtrace 2 and length 5 are $\{00122, 00212, 00221, 01022, 01202, 02021\}$.
Enumeration (OEIS)