# 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$.

 1 2 3 4 5 6 7 8 9 10 (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 0 0 0 1 0 0 0 1 0 2 0 0 2 2 0 2 0 2 0 4 6 0 6 6 0 6 4 4 0 8 24 8 24 16 16 16 16 16 0 56 80 40 80 40 80 56 80 56 40 272 272 240 240 192 320 192 320 272 240 1184 896 1120 896 896 1184 896 1120 1184 1120 4763 3584 4480 3584 4096 4096 4096 4096 4608 4608 17536 15360 17536 15360 17536 15360 17536 15360 17536 17536 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.