5-ary words of given trace and subtrace.

Here we consider the set S(n;t,s) of length n words a₁a₂···a_n over the alphabet {0,1,2,3,4} that have trace t and subtrace s. The trace of a 5-ary word is the sum of its digits mod 5, i.e. t = a₁+a₂+ ··· +a_n mod 5. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken mod 5, i.e. s = SUM( a_ia_j : 1 < i < j < n ).

	(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 }.

Further Notes:

The number S(n;t,s) can be computed from the following recurrence relation
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)
Column (0,0) is sequence A073963 in Neil J. Sloane's database of integer sequences.
Column (0,1),(0,4) is sequence A073964 in Neil J. Sloane's database of integer sequences.
Column (0,2),(0,3) is sequence A073965 in Neil J. Sloane's database of integer sequences.
Column (1,0),(2,0),(3,0),(4,0) is sequence A073966 in Neil J. Sloane's database of integer sequences.
Column (1,1),(2,4),(3,4),(4,1) is sequence A073967 in Neil J. Sloane's database of integer sequences.
Column (1,2),(2,3),(3,3),(4,2) is sequence A073968 in Neil J. Sloane's database of integer sequences.
Column (1,3),(2,2),(3,2),(4,3) is sequence A073969 in Neil J. Sloane's database of integer sequences.
Column (1,4),(2,1),(3,1),(4,4) is sequence A073970 in Neil J. Sloane's database of integer sequences.
These numbers are defined and used in a more general setting in the papers:
C.R. Miers and F. Ruskey, Counting Strings with Given Elementary Symmetric Function Evaluations I: Strings over Zp with p Prime, SIAM J. Discrete Mathematics, 17 (2004) 675-685.
C.R. Miers and F. Ruskey, Counting Strings with Given Elementary Symmetric Function Evaluations II: Circular Strings, SIAM J. Discrete Mathematics, 18 (2004) 71-82.

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Saturday, 19-May-2007 23:22:40 PDT.
There have been 1619 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.