Lyndon words over $GF(4)$ 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(4)$ 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$.
Below we use $a=\operatorname{root}(x^2+x+1)$ and $b=1+a$.
| (trace,subtrace) |
$n$
| (0,0)
| (0,1) (0,$a$) (0,$b$)
| (1,0) ($a$,0) ($b$,0)
| (1,1) ($a$,$b$) ($b$,$a$)
| (1,$a$) (1,$b$) ($a$,1) ($a$,$a$) ($b$,1) ($b$,$b$)
|
1 |
1 | 0
| 1 | 0
| 0
|
---|
2 |
0 | 0
| 1 | 1
| 0
|
---|
3 |
2 | 1
| 1 | 2
| 1
|
---|
4 |
6 | 2
| 4 | 4
| 4
|
---|
5 |
15 | 12
| 15 | 12
| 12
|
---|
6 |
40 | 40
| 45 | 45
| 40
|
---|
7 |
153 | 144
| 144 | 153
| 144
|
---|
8 |
528 | 496
| 512 | 512
| 512
|
---|
9 |
1841 | 1813
| 1841 | 1813
| 1813
|
---|
10 |
6528 | 6528
| 6579 | 6579
| 6528
|
---|
11 |
23901 | 23808
| 23808 | 23901
| 23808
|
---|
12 |
87550 | 87210
| 87380 | 87380
| 87380
|
---|
13 |
322875 | 322560
| 322875 | 322560
| 322560
|
---|
14 |
1198080 | 1198080
| 1198665 | 1198665
| 1198080
|
---|
15 |
4474738 | 4473647
| 4473647 | 4474738
| 4473647
|
---|
Examples
The one 4-ary Lyndon word of trace $b$, subtrace $a$ and length 2 is $\{1a\}$.
The two 4-ary Lyndon words of trace 0, subtrace 0 and length 3 are $\{123, 132\}$.
The two 4-ary Lyndon words of trace 0, subtrace 1 and length 4 are $\{0011, 11aa\}$.
Enumeration (OEIS)
-
Column (0,0) is OEIS A074446.
-
Column (0,1),(0,$a$),(0,$b$) is OEIS A074447.
-
Column (1,0),($a$,0),($b$,0) is OEIS A074448.
-
Column (1,1),($a$,$b$),($b$,$a$) is OEIS A074449.
-
Column (1,$a$),(1,$b$),($a$,1),($a$,$a$),($b$,1),($b$,$b$) is OEIS A074450.