5-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=5$ 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,4)
| (0,2)
(0,3)
| (1,0)
(2,0)
(3,0)
(4,0)
| (1,1)
(2,4)
(3,4)
(4,1)
| (1,2)
(2,3)
(3,3)
(4,2)
| (1,3)
(2,2)
(3,2)
(4,3)
| (1,4)
(2,1)
(3,1)
(4,4)
|
| 1 |
1 | 0 | 0
| 1
| 0 | 0 | 0
| 0
|
|---|
| 2 |
0 | 1 | 0
| 1
| 0 | 0 | 1
| 0
|
|---|
| 3 |
0 | 2 | 2
| 2
| 2 | 0 | 2
| 2
|
|---|
| 4 |
6 | 5 | 7
| 5
| 6 | 5 | 7
| 7
|
|---|
| 5 |
24 | 20 | 30
| 25
| 25 | 25 | 25
| 25
|
|---|
| 6 |
104 | 99 | 107
| 104
| 99 | 107 | 107
| 99
|
|---|
| 7 |
432 | 450 | 450
| 450
| 450 | 450 | 450
| 432
|
|---|
| 8 |
1950 | 1965 | 1935
| 1935
| 1965 | 1950 | 1965
| 1935
|
|---|
| 9 |
8736 | 8666 | 8666
| 8666
| 8736 | 8666 | 8666
| 8666
|
|---|
| 10 |
39298 | 38985 | 38990
| 39050
| 39050 | 39050 | 39050
| 39050
|
|---|
| 11 |
177784 | 177500 | 177500
| 177784
| 177500 | 177500 | 177500
| 177500
|
|---|
| 12 |
813748 | 814006 | 813490
| 814006
| 813490 | 813490 | 814006
| 813748
|
|---|
| 13 |
3755048 | 3756250 | 3756250
| 3756250
| 3756250 | 3755048 | 3756250
| 3756250
|
|---|
| 14 |
17438400 | 17437275 | 17439507
| 17437275
| 17438400 | 17437275 | 17439507
| 17439507
|
|---|
| 15 |
81380192 | 81374990 | 81385410
| 81380200
| 81380200 | 81380200 | 81380200
| 81380200
|
|---|
Examples
The two 5-ary Lyndon words of trace 2, subtrace 4 and length 3 are $\{124, 142\}$.
The five 5-ary Lyndon words of trace 1, subtrace 2 and length 4 are $\{0222, 1113, 1244, 1424, 1442\}$.
The seven 5-ary Lyndon words of trace 3, subtrace 1 and length 4 are $\{0044, 0233, 0323, 0332, 1124, 1142, 1214\}$.
Enumeration (OEIS)
-
Column (0,0) is OEIS A074414.
-
Column (0,1),(0,4) is OEIS A074415.
-
Column (0,2),(0,3) is OEIS A074416.
-
Column (1,0),(2,0),(3,0),(4,0) is OEIS A074417.
-
Column (1,1),(2,4),(3,4),(4,1) is OEIS A074418.
-
Column (1,2),(2,3),(3,3),(4,2) is OEIS A074419.
-
Column (1,3),(2,2),(3,2),(4,3) is OEIS A074420.
-
Column (1,4),(2,1),(3,1),(4,4) is OEIS A074421.