6-ary 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=6$ 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)
| (0,2)
| (0,3)
| (0,4)
| (0,5)
| (1,0) (5,0)
| (1,1) (5,1)
| (1,2) (5,2)
| (1,3) (5,3)
| (1,4) (5,4)
| (1,5) (5,5)
| (2,0) (4,0)
| (2,1) (4,1)
| (2,2) (4,2)
| (2,3) (4,3)
| (2,4) (4,4)
| (2,5) (4,5)
| (3,0)
| (3,1)
| (3,2)
| (3,3)
| (3,4)
| (3,5)
|
1 |
1 | 0 | 0
| 0 | 0 | 0
| 1 | 0 | 0
| 0 | 0 | 0
| 1 | 0 | 0
| 0 | 0 | 0
| 1 | 0 | 0
| 0 | 0 | 0
|
---|
2 |
0 | 0 | 1
| 0 | 0 | 1
| 2 | 0 | 0
| 0 | 1 | 0
| 1 | 0 | 0
| 1 | 0 | 0
| 1 | 0 | 2
| 0 | 0 | 0
|
---|
3 |
0 | 0 | 2
| 3 | 0 | 6
| 3 | 1 | 3
| 1 | 3 | 1
| 1 | 3 | 1
| 3 | 1 | 3
| 3 | 0 | 6
| 0 | 0 | 2
|
---|
4 |
4 | 8 | 6
| 13 | 2 | 18
| 9 | 6 | 12
| 9 | 6 | 12
| 4 | 8 | 6
| 13 | 2 | 18
| 9 | 6 | 12
| 9 | 6 | 12
|
---|
5 |
25 | 60 | 36
| 42 | 36 | 60
| 36 | 42 | 36
| 60 | 25 | 60
| 36 | 42 | 36
| 60 | 25 | 60
| 25 | 60 | 36
| 42 | 36 | 60
|
---|
6 |
165 | 236 | 240
| 165 | 236 | 240
| 162 | 270 | 162
| 270 | 162 | 270
| 214 | 214 | 214
| 214 | 214 | 214
| 126 | 300 | 180
| 207 | 180 | 300
|
---|
7 |
1157 | 1008 | 1296
| 900 | 1296 | 1008
| 900 | 1296 | 1008
| 1157 | 1008 | 1296
| 1157 | 1008 | 1296
| 900 | 1296 | 1008
| 900 | 1296 | 1008
| 1157 | 1008 | 1296
|
---|
8 |
6552 | 5280 | 6312
| 5094 | 6792 | 4908
| 5616 | 5832 | 6048
| 5616 | 5832 | 6048
| 6312 | 5094 | 6792
| 4908 | 6552 | 5280
| 5832 | 6048 | 5616
| 5832 | 6048 | 5616
|
---|
9 |
33045 | 30240 | 31824
| 29151 | 34272 | 28080
| 33048 | 29160 | 33048
| 29160 | 33048 | 29160
| 33048 | 29160 | 33048
| 29160 | 33048 | 29160
| 33045 | 30240 | 31824
| 29151 | 34272 | 28080
|
---|
10 |
167928 | 169987 | 165840
| 167928 | 169987 | 165840
| 178459 | 159408 | 176256
| 157464 | 180662 | 155520
| 167928 | 169987 | 165840
| 167928 | 169987 | 165840
| 178459 | 159408 | 176256
| 157464 | 180662 | 155520
|
---|
Examples
The three 6-ary Lyndon words of trace 2, subtrace 1 and length 3 are $\{011, 134, 143\}$.
The two 6-ary Lyndon words of trace 3, subtrace 5 and length 3 are $\{135, 153\}$.
The six 6-ary Lyndon words of trace 5, subtrace 1 and length 4 are $\{0113, 0131, 0311, 1334, 1343, 1433\}$.
Enumeration (OEIS)
-
Column (0,0) is OEIS A074422.
-
Column (0,1) is OEIS A074423.
-
Column (0,2) is OEIS A074424.
-
Column (0,3) is OEIS A074425.
-
Column (0,4) is OEIS A074426.
-
Column (0,5) is OEIS A074427.
-
Column (1,0),(5,0) is OEIS A074428.
-
Column (1,1),(5,1) is OEIS A074429.
-
Column (1,2),(5,2) is OEIS A074430.
-
Column (1,3),(5,3) is OEIS A074431.
-
Column (1,4),(5,4) is OEIS A074432.
-
Column (1,5),(5,5) is OEIS A074433.
-
Column (2,0),(4,0) is OEIS A074434.
-
Column (2,1),(4,1) is OEIS A074435.
-
Column (2,2),(4,2) is OEIS A074436.
-
Column (2,3),(4,3) is OEIS A074437.
-
Column (2,4),(4,4) is OEIS A074438.
-
Column (2,5),(4,5) is OEIS A074439.
-
Column (3,0) is OEIS A074440.
-
Column (3,1) is OEIS A074441.
-
Column (3,2) is OEIS A074442.
-
Column (3,3) is OEIS A074443.
-
Column (3,4) is OEIS A074444.
-
Column (3,5) is OEIS A074445.