# 5-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=5$ 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 (trace,subtrace) $n$ (0,0) (0,1)(0,4) (0,2)(0,3) (1,0)(2,0)(3,0)(4,0) (1,1)(2,4)(3,4)(4,1) (1,2)(2,3)(3,3)(4,2) (1,3)(2,2)(3,2)(4,3) (1,4)(2,1)(3,1)(4,4) 1 0 0 1 0 0 0 0 1 2 0 2 0 0 2 1 1 6 6 6 6 1 6 6 25 20 30 20 25 20 30 30 125 100 150 125 125 125 125 125 625 600 650 625 600 650 650 600 3025 3150 3150 3150 3150 3150 3150 3025 15625 15750 15500 15500 15750 15625 15750 15500 78625 78000 78000 78000 78625 78000 78000 78000 393125 390000 390000 390625 390625 390625 390625 390625

## Examples

The two 5-ary strings of trace 0, subtrace 4 and length 2 are $\{14, 41\}$. The two 5-ary strings of trace 3, subtrace 2 and length 2 are $\{12, 21\}$. The one 5-ary string of trace 1, subtrace 2 and length 3 is $\{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-4,s-4(t-4)) \\ &= S(n-1;t,s) + S(n-1;t+4,s+4t+1) + S(n-1;t+3,s+3t+4) + S(n-1;t+2,s+2t+4) + S(n-1;t+1,s+t+1). \end{align}
• Column (0,0) is OEIS A073963.
• Column (0,1),(0,4) is OEIS A073964.
• Column (0,2),(0,3) is OEIS A073965.
• Column (1,0),(2,0),(3,0),(4,0) is OEIS A073966.
• Column (1,1),(2,4),(3,4),(4,1) is OEIS A073967.
• Column (1,2),(2,3),(3,3),(4,2) is OEIS A073968.
• Column (1,3),(2,2),(3,2),(4,3) is OEIS A073969.
• Column (1,4),(2,1),(3,1),(4,4) is OEIS A073970.