Binary Lyndon words with given trace and subtrace
A $k$-ary
Lyndon word is a string made from the characters $\{0,1,\ldots,k-1\}$.
It must be aperiodic (not equal to any of its non-trivial rotations) and be lexicographically least among its rotations.
Here we consider the number $L(n;t,s)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet $\{0,1,\ldots,k-1\}$ with $k=2$ that have trace $t$ and subtrace $s$.
The
trace of a Lyndon word is the sum of its digits mod $k$, i.e., $t = a_1 + a_2 + \cdots + a_n \pmod{k}$.
The
subtrace is the sum of the products of all $n(n-1)/2$ pairs of digits taken mod $k$, i.e., $s=\sum_{1\leq i\lt j\leq n} a_i a_j$.
|
| (trace,subtrace) |
| $n$
| (0,0)
| (0,1)
| (1,0)
| (1,1)
|
| 1 |
1 | 0 | 1
| 0
|
|---|
| 2 |
0 | 0 | 1
| 0
|
|---|
| 3 |
0 | 1 | 1
| 0
|
|---|
| 4 |
0 | 1 | 1
| 1
|
|---|
| 5 |
1 | 2 | 1
| 2
|
|---|
| 6 |
2 | 2 | 2
| 3
|
|---|
| 7 |
5 | 4 | 4
| 5
|
|---|
| 8 |
8 | 6 | 8
| 8
|
|---|
| 9 |
15 | 13 | 15
| 13
|
|---|
| 10 |
24 | 24 | 27
| 24
|
|---|
| 11 |
45 | 48 | 48
| 45
|
|---|
| 12 |
80 | 85 | 85
| 85
|
|---|
| 13 |
155 | 160 | 155
| 160
|
|---|
| 14 |
288 | 288 | 288
| 297
|
|---|
| 15 |
550 | 541 | 541
| 550
|
|---|
| 16 |
1024 | 1008 | 1024
| 1024
|
|---|
| 17 |
1935 | 1920 | 1935
| 1920
|
|---|
| 18 |
3626 | 3626 | 3654
| 3626
|
|---|
| 19 |
6885 | 6912 | 6912
| 6885
|
|---|
| 20 |
13056 | 13107 | 13107
| 13107
|
|---|
Examples
The one binary Lyndon word of trace 1, subtrace 0 and length 3 is $\{001\}$.
The two binary Lyndon words of trace 0, subtrace 1 and length 5 are $\{00011, 00101\}$.
The two binary Lyndon words of trace 0, subtrace 0 and length 6 are $\{001111, 010111\}$.
Enumeration (OEIS)