6-ary words with given trace and subtrace
Here we consider the number $S(n;t,s)$ of length $n$ 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 $k$-ary 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 |
1 | 0 | 2
| 1 | 0 | 2
| 4 | 0 | 0
| 0 | 2 | 0
| 2 | 1 | 0
| 2 | 1 | 0
| 2 | 0 | 4
| 0 | 0 | 0
|
|---|
| 3 |
3 | 0 | 6
| 9 | 0 | 18
| 9 | 3 | 9
| 3 | 9 | 3
| 3 | 9 | 3
| 9 | 3 | 9
| 9 | 0 | 18
| 3 | 0 | 6
|
|---|
| 4 |
18 | 36 | 24
| 54 | 12 | 72
| 36 | 24 | 48
| 36 | 24 | 48
| 18 | 36 | 24
| 54 | 12 | 72
| 36 | 24 | 48
| 36 | 24 | 48
|
|---|
| 5 |
126 | 300 | 180
| 210 | 180 | 300
| 180 | 210 | 180
| 300 | 126 | 300
| 180 | 210 | 180
| 300 | 126 | 300
| 126 | 300 | 180
| 210 | 180 | 300
|
|---|
| 6 |
1008 | 1440 | 1440
| 1008 | 1440 | 1440
| 972 | 1620 | 972
| 1620 | 972 | 1620
| 1296 | 1296 | 1296
| 1296 | 1296 | 1296
| 756 | 1800 | 1080
| 1260 | 1080 | 1800
|
|---|
| 7 |
8100 | 7056 | 9072
| 6300 | 9072 | 7056
| 6300 | 9072 | 7056
| 8100 | 7056 | 9072
| 8100 | 7056 | 9072
| 6300 | 9072 | 7056
| 6300 | 9072 | 7056
| 8100 | 7056 | 9072
|
|---|
| 8 |
52488 | 42336 | 50544
| 40824 | 54432 | 39312
| 44928 | 46656 | 48384
| 44928 | 46656 | 48384
| 50544 | 40824 | 54432
| 39312 | 52488 | 42336
| 46656 | 48384 | 44928
| 46656 | 48384 | 44928
|
|---|
| 9 |
297432 | 272160 | 286416
| 262440 | 308448 | 252720
| 297432 | 262440 | 297432
| 262440 | 297432 | 262440
| 297432 | 262440 | 297432
| 262440 | 297432 | 262440
| 297432 | 272160 | 286416
| 262440 | 308448 | 252720
|
|---|
| 10 |
1679616 | 1700352 | 1658880
| 1679616 | 1700352 | 1658880
| 1784592 | 1594080 | 1762560
| 1574640 | 1806624 | 1555200
| 1679616 | 1700352 | 1658880
| 1679616 | 1700352 | 1658880
| 1784592 | 1594080 | 1762560
| 1574640 | 1806624 | 1555200
|
|---|
Examples
The two 6-ary strings of trace 0, subtrace 2 and length 2 are $\{24, 42\}$.
The two 6-ary strings of trace 5, subtrace 4 and length 2 are $\{14, 41\}$.
The three 6-ary strings of trace 1, subtrace 5 and length 3 are $\{115, 151, 511\}$.
Enumeration (OEIS)
-
The number $S(n;t,s)$ can be computed from the following recurrence relation
\begin{align}
S(n;t,s) &= S(n-1;t,s) + S(n-1;t-1,s-(t-1)) + S(n-1;t-2,s-2(t-2)) + S(n-1;t-3,s-3(t-3)) + S(n-1;t-4,s-4(t-4)) + S(n-1;t-5,s-5(t-5)) \\
&= S(n-1;t,s) + S(n-1;t+5,s+5t+1) + S(n-1;t+4,s+4t+4) + S(n-1;t+3,s+3t+3) + S(n-1;t+2,s+2t+2) + S(n-1;t+1,s+t+1).
\end{align}
-
Column (0,0) is OEIS A073971.
-
Column (0,1) is OEIS A073972.
-
Column (0,2) is OEIS A073973.
-
Column (0,3) is OEIS A073974.
-
Column (0,4) is OEIS A073975.
-
Column (0,5) is OEIS A073976.
-
Column (1,0),(5,0) is OEIS A073977.
-
Column (1,1),(5,1) is OEIS A073978.
-
Column (1,2),(5,2) is OEIS A073979.
-
Column (1,3),(5,3) is OEIS A073980.
-
Column (1,4),(5,4) is OEIS A073981.
-
Column (1,5),(5,5) is OEIS A073982.
-
Column (2,0),(4,0) is OEIS A073983.
-
Column (2,1),(4,1) is OEIS A073984.
-
Column (2,2),(4,2) is OEIS A073985.
-
Column (2,3),(4,3) is OEIS A073986.
-
Column (2,4),(4,4) is OEIS A073987.
-
Column (2,5),(4,5) is OEIS A073988.
-
Column (3,0) is OEIS A073989.
-
Column (3,1) is OEIS A073990.
-
Column (3,2) is OEIS A073991.
-
Column (3,3) is OEIS A073992.
-
Column (3,4) is OEIS A073993.
-
Column (3,5) is OEIS A073994.