4-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=4$ 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)
| (1,0)
(3,0)
| (1,1)
(3,1)
| (1,2)
(3,2)
| (1,3)
(3,3)
| (2,0)
| (2,1)
| (2,2)
| (2,3)
|
| 1 |
1 | 0 | 0 | 0
| 1 | 0 | 0 | 0
| 1 | 0 | 0 | 0
|
|---|
| 2 |
0 | 0 | 0 | 1
| 1 | 0 | 1 | 0
| 1 | 0 | 0 | 0
|
|---|
| 3 |
1 | 2 | 0 | 2
| 2 | 0 | 2 | 1
| 1 | 2 | 0 | 2
|
|---|
| 4 |
1 | 6 | 1 | 6
| 4 | 4 | 4 | 4
| 4 | 4 | 0 | 6
|
|---|
| 5 |
11 | 16 | 8 | 16
| 8 | 16 | 11 | 16
| 11 | 16 | 8 | 16
|
|---|
| 6 |
44 | 45 | 36 | 40
| 32 | 53 | 32 | 53
| 45 | 36 | 40 | 44
|
|---|
| 7 |
169 | 128 | 160 | 128
| 128 | 169 | 128 | 160
| 169 | 128 | 160 | 128
|
|---|
| 8 |
588 | 448 | 548 | 448
| 512 | 512 | 512 | 512
| 576 | 440 | 576 | 440
|
|---|
| 9 |
1948 | 1706 | 1920 | 1706
| 1948 | 1706 | 1920 | 1706
| 1948 | 1706 | 1920 | 1706
|
|---|
| 10 |
6560 | 6528 | 6496 | 6579
| 6963 | 6144 | 6963 | 6144
| 6579 | 6560 | 6528 | 6496
|
|---|
| 11 |
23133 | 24576 | 23040 | 24576
| 24576 | 23040 | 24576 | 23133
| 23133 | 24576 | 23040 | 24576
|
|---|
| 12 |
84565 | 90110 | 84565 | 90110
| 87380 | 87380 | 87380 | 87380
| 84820 | 90046 | 84480 | 90004
|
|---|
| 13 |
317755 | 327680 | 317440 | 327680
| 317440 | 327680 | 317755 | 327680
| 317755 | 327680 | 317440 | 327680
|
|---|
| 14 |
1198336 | 1198665 | 1197824 | 1198080
| 1179648 | 1217097 | 1179648 | 1217097
| 1198665 | 1197824 | 1198080 | 1198336
|
|---|
Examples
The two 4-ary Lyndon words of trace 1, subtrace 2 and length 3 are $\{023, 032\}$.
The four 4-ary Lyndon words of trace 3, subtrace 3 and length 4 are $\{0111, 0133, 0313, 0331\}$.
The six 4-ary Lyndon words of trace 2, subtrace 3 and length 4 are $\{0123, 0132, 0213, 0231, 0312, 0321\}$.
Enumeration (OEIS)
-
If $n$ is odd OR $t$ is odd OR $t = 0 \pmod{4}$ and $s$ is odd OR $t = 2 \pmod{4}$ and $s$ is even, then the numbers above are
\[
L(n;t,s) = \frac{1}{n} \sum_{j=0,1,2,3} \sum_{\substack{d\vert n \\ d=2j+1 \pmod{8}}} \mu(d) S(n/d,(-1)^j t,(-1)^j s-jt^2),
\]
where $S(n;t,s)$ is the number of 4-ary words with trace $t$ and subtrace $s$.
In the case where $t$ is odd, this formula may be simplified to
\[
L(n;t,s) = \frac{1}{n} \sum_{\substack{d \vert n \\ d=1,3 \pmod{4}}} \mu(d) S(n/d, dt, ds-(d-1)/2).
\]
-
Column (0,0) is OEIS A068596.
-
Column (0,1) is OEIS A074403.
-
Column (0,2) is OEIS A074404.
-
Column (0,3) is OEIS A074405.
-
Column (1,0),(3,0) is OEIS A074406.
-
Column (1,1),(3,1) is OEIS A074407.
-
Column (1,2),(3,2) is OEIS A074408.
-
Column (1,3),(3,3) is OEIS A074409.
-
Column (2,0) is OEIS A074410.
-
Column (2,1) is OEIS A074411.
-
Column (2,2) is OEIS A074412.
-
Column (2,3) is OEIS A074413.