6-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,5} that have trace t and subtrace s. The trace of a 6-ary word is the sum of its digits mod 6, i.e. t = a₁+a₂+ ··· +a_n mod 6. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken mod 6, i.e. s = SUM( a_ia_j : 1 < i < j < n ).

	(trace,subtrace)
n	(0,0)	(0,1)	(0,2)	(0,3)	(0,4)	(0,5)	(1,0) (5,0)	(1,1) (5,1)	(1,2) (5,2)	(1,3) (5,3)	(1,4) (5,4)	(1,5) (5,5)	(2,0) (4,0)	(2,1) (4,1)	(2,2) (4,2)	(2,3) (4,3)	(2,4) (4,4)	(2,5) (4,5)	(3,0)	(3,1)	(3,2)	(3,3)	(3,4)	(3,5)
1	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0
2	1	0	2	1	0	2	4	0	0	0	2	0	2	1	0	2	1	0	2	0	4	0	0	0
3	3	0	6	9	0	18	9	3	9	3	9	3	3	9	3	9	3	9	9	0	18	3	0	6
4	18	36	24	54	12	72	36	24	48	36	24	48	18	36	24	54	12	72	36	24	48	36	24	48
5	126	300	180	210	180	300	180	210	180	300	126	300	180	210	180	300	126	300	126	300	180	210	180	300
6	1008	1440	1440	1008	1440	1440	972	1620	972	1620	972	1620	1296	1296	1296	1296	1296	1296	756	1800	1080	1260	1080	1800
7	8100	7056	9072	6300	9072	7056	6300	9072	7056	8100	7056	9072	8100	7056	9072	6300	9072	7056	6300	9072	7056	8100	7056	9072
8	52488	42336	50544	40824	54432	39312	44928	46656	48384	44928	46656	48384	50544	40824	54432	39312	52488	42336	46656	48384	44928	46656	48384	44928
9	297432	272160	286416	262440	308448	252720	297432	262440	297432	262440	297432	262440	297432	262440	297432	262440	297432	262440	297432	272160	286416	262440	308448	252720
10	1679616	1700352	1658880	1679616	1700352	1658880	1784592	1594080	1762560	1574640	1806624	1555200	1679616	1700352	1658880	1679616	1700352	1658880	1784592	1594080	1762560	1574640	1806624	1555200

Examples:

The two 6-ary strings of trace 0, subtrace 2 and length 2 are { 24, 42 }.
The two 6-ary strings of trace 5, subtrace 4 and length 2 are { 14, 41 }.
The three 6-ary strings of trace 1, subtrace 5 and length 3 are { 115, 151, 511 }.

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-5,s-5(t-5))
= S(n-1;t,s) + S(n-1;t+5,s+5t+1) + S(n-1;t+4,s+4t+4) + S(n-1;t+3,s+3t+3) + S(n-1;t+2,s+2t+2) + S(n-1;t+1,s+t+1)
Column (0,0) is sequence A073971 in Neil J. Sloane's database of integer sequences.
Column (0,1) is sequence A073972 in Neil J. Sloane's database of integer sequences.
Column (0,2) is sequence A073973 in Neil J. Sloane's database of integer sequences.
Column (0,3) is sequence A073974 in Neil J. Sloane's database of integer sequences.
Column (0,4) is sequence A073975 in Neil J. Sloane's database of integer sequences.
Column (0,5) is sequence A073976 in Neil J. Sloane's database of integer sequences.
Column (1,0),(5,0) is sequence A073977 in Neil J. Sloane's database of integer sequences.
Column (1,1),(5,1) is sequence A073978 in Neil J. Sloane's database of integer sequences.
Column (1,2),(5,2) is sequence A073979 in Neil J. Sloane's database of integer sequences.
Column (1,3),(5,3) is sequence A073980 in Neil J. Sloane's database of integer sequences.
Column (1,4),(5,4) is sequence A073981 in Neil J. Sloane's database of integer sequences.
Column (1,5),(5,5) is sequence A073982 in Neil J. Sloane's database of integer sequences.
Column (2,0),(4,0) is sequence A073983 in Neil J. Sloane's database of integer sequences.
Column (2,1),(4,1) is sequence A073984 in Neil J. Sloane's database of integer sequences.
Column (2,2),(4,2) is sequence A073985 in Neil J. Sloane's database of integer sequences.
Column (2,3),(4,3) is sequence A073986 in Neil J. Sloane's database of integer sequences.
Column (2,4),(4,4) is sequence A073987 in Neil J. Sloane's database of integer sequences.
Column (2,5),(4,5) is sequence A073988 in Neil J. Sloane's database of integer sequences.
Column (3,0) is sequence A073989 in Neil J. Sloane's database of integer sequences.
Column (3,1) is sequence A073990 in Neil J. Sloane's database of integer sequences.
Column (3,2) is sequence A073991 in Neil J. Sloane's database of integer sequences.
Column (3,3) is sequence A073992 in Neil J. Sloane's database of integer sequences.
Column (3,4) is sequence A073993 in Neil J. Sloane's database of integer sequences.
Column (3,5) is sequence A073994 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:31:14 PDT.
There have been 925 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.