Ternary 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=3$ 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)
| (1,0)
(2,0)
| (1,1)
(2,1)
| (1,2)
(2,2)
|
| 1 |
1 | 0 | 0
| 1 | 0 | 0
|
|---|
| 2 |
1 | 0 | 2
| 2 | 1 | 0
|
|---|
| 3 |
3 | 0 | 6
| 3 | 3 | 3
|
|---|
| 4 |
9 | 6 | 12
| 9 | 6 | 12
|
|---|
| 5 |
21 | 30 | 30
| 30 | 21 | 30
|
|---|
| 6 |
63 | 90 | 90
| 81 | 81 | 81
|
|---|
| 7 |
225 | 252 | 252
| 225 | 252 | 252
|
|---|
| 8 |
729 | 756 | 702
| 702 | 729 | 756
|
|---|
| 9 |
2187 | 2268 | 2106
| 2187 | 2187 | 2187
|
|---|
| 10 |
6561 | 6642 | 6480
| 6561 | 6642 | 6480
|
|---|
| 11 |
19845 | 19602 | 19602
| 19602 | 19845 | 19602
|
|---|
| 12 |
59535 | 58806 | 58806
| 59049 | 59049 | 59049
|
|---|
| 13 |
177633 | 176904 | 176904
| 177633 | 176904 | 176904
|
|---|
| 14 |
531441 | 530712 | 532170
| 532170 | 531441 | 530712
|
|---|
| 15 |
1594323 | 1592136 | 1596510
| 1594323 | 1594323 | 1594323
|
|---|
| 16 |
4782969 | 4780782 | 4785156
| 4782969 | 4780782 | 4785156
|
|---|
| 17 |
14344533 | 14351094 | 14351094
| 14351094 | 14344533 | 14351094
|
|---|
| 18 |
43033599 | 43053282 | 43053282
| 43046721 | 43046721 | 43046721
|
|---|
| 19 |
129127041 | 129146724 | 129146724
| 129127041 | 129146724 | 129146724
|
|---|
| 20 |
387420489 | 387440172 | 387400806
| 387400806 | 387420489 | 387440172
|
|---|
Examples
The one ternary string of trace 2, subtrace 1 and length 2 is $\{11\}$.
The three ternary strings of trace 0, subtrace 0 and length 3 are $\{000, 111, 222\}$.
The three ternay strings of trace 1, subtrace 2 and length 3 are $\{112, 121, 211\}$.
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,s) + S(n-1;t+2,s+2t+1) + S(n-1;t+1,s+t+1).
\end{align}
Column (0,0) is OEIS A073947.
The sequence has the rational generating function $(x-1)^2 ((x-1)^3 +5x^3 ) / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
Column (0,1) is OEIS A073948.
The sequence has the rational generating function $6x^4 (x-1) / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
Column (0,2) is OEIS A073949.
The sequence has the rational generating function $2x^2 ((x-1)^3 +2x^3 ) / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
Column (1,0),(2,0) is OEIS A073950.
The sequence has the rational generating function $-x(x-1)((x-1)^3 +2x^3 ) / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
Column (1,1),(2,1) is OEIS A073951.
The sequence has the rational generating function $x^2 ((x-1)^3 - 4x^3 ) / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
Column (1,2),(2,2) is OEIS A073952.
The sequence has the rational generating function $-3x^3 (x-1)^2 / (3x-1)(3x^2 +1)(3x^2 -3x+1)$.
These numbers are defined and used in a more general setting in the papers [MR04a] and [MR04b].
References
-
[MR04a] C. R. Miers and F. Ruskey. Counting strings with given elementary symmetric function evaluations. I. Strings over $Z_p$ with $p$ prime. SIAM J. Discrete Math., 17(4):675–685, 2004.
-
[MR04b] C. R. Miers and F. Ruskey. Counting strings with given elementary symmetric function evaluations. II. Circular strings. SIAM J. Discrete Math., 18(1):71–82, 2004.