4-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=4$ 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)
(2,3)
| (0,2)
| (0,3)
(2,1)
| (1,0)
(3,0)
| (1,1)
(3,1)
| (1,2)
(3,2)
| (1,3)
(3,3)
| (2,0)
| (2,2)
|
| 1 |
1 | 0 | 0 | 0
| 1 | 0 | 0 | 0
| 1 | 0
|
|---|
| 2 |
2 | 0 | 0 | 2
| 2 | 0 | 2 | 0
| 2 | 0
|
|---|
| 3 |
4 | 6 | 0 | 6
| 6 | 0 | 6 | 4
| 4 | 0
|
|---|
| 4 |
8 | 24 | 8 | 24
| 16 | 16 | 16 | 16
| 16 | 0
|
|---|
| 5 |
56 | 80 | 40 | 80
| 40 | 80 | 56 | 80
| 56 | 40
|
|---|
| 6 |
272 | 272
| 240 | 240
| 192 | 320
| 192 | 320
| 272
| 240
|
|---|
| 7 |
1184 | 896
| 1120 | 896
| 896 | 1184
| 896 | 1120
| 1184
| 1120
|
|---|
| 8 |
4763 | 3584
| 4480 | 3584
| 4096 | 4096
| 4096 | 4096
| 4608
| 4608
|
|---|
| 9 |
17536 | 15360
| 17536 | 15360
| 17536 | 15360
| 17536 | 15360
| 17536
| 17536
|
|---|
| 10 |
65792 | 65280
| 65280 | 65792
| 69632 | 61440
| 69632 | 61440
| 65792
| 65280
|
|---|
Examples
The two 4-ary strings of trace 0, subtrace 3 and length 2 are $\{13, 31\}$.
The four 4-ary strings of trace 0, subtrace 0 and length 3 are $\{000, 022, 202, 220\}$.
The four 4-ary strings of trace 2, subtrace 0 and length 3 are $\{002, 020, 200, 222\}$.
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,s) + S(n-1;t+3,s+3t+1) + S(n-1;t+2,s+2t) + S(n-1;t+1,s+t+1).
\end{align}
-
$S(n;1,s) = S(n;3,s)$ follows from the bijection that swaps each digit of the string with its negation.
-
It appears that
$S(n;0,1) = S(n;2,3)$ and $S(n;0,3) = S(n;2,1)$. Proof?
-
Each column is a sequence whose ordinary generating function is rational with denominator $D=(4z-1)(8z^2-4z+1)(16z^4+1)(2z-1)$.
-
Column (0,0) is OEIS A068620.
The numerator of the ordinary generating function is $1+32z^2+48z^4+352z^6-576z^7-56z^3-104z^5-9z+320z^8$.
-
Column (0,1),(2,3) is OEIS A068711.
-
Column (0,2) is OEIS A068774.
-
Column (0,3),(2,1) is OEIS A068777.
-
Column (1,0),(3,0) is OEIS A068786.
-
Column (1,1),(3,1) is OEIS A068778.
-
Column (1,2),(3,2) is OEIS A068787.
-
Column (1,3),(3,3) is OEIS A068788.
-
Column (2,0) is OEIS A068789.
-
Column (2,2) is OEIS A068790.
-
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.