The Combinatorial Object Server

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

	(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	1	0	0	1	0	0	0	0
2	1	2	0	2	0	0	2	1
3	1	6	6	6	6	1	6	6
4	25	20	30	20	25	20	30	30
5	125	100	150	125	125	125	125	125
6	625	600	650	625	600	650	650	600
7	3025	3150	3150	3150	3150	3150	3150	3025
8	15625	15750	15500	15500	15750	15625	15750	15500
9	78625	78000	78000	78000	78625	78000	78000	78000
10	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.