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

	(trace,subtrace)
n	(0,0)	(0,1)	(0,2)	(0,3)	(1,0) (3,0)	(1,1) (3,1)	(1,2) (3,2)	(1,3) (3,3)	(2,0)	(2,1)	(2,2)	(2,3)
1	1	0	0	0	1	0	0	0	1	0	0	0
2	2	0	0	2	2	0	2	0	2	2	0	0
3	4	6	0	6	6	0	6	4	4	6	0	6
4	8	24	8	24	16	16	16	16	16	24	0	24
5	56	80	40	80	40	80	56	80	56	80	40	80
6	272	272	240	240	192	320	192	320	272	240	240	272
7	1184	896	1120	896	896	1184	896	1120	1184	896	1120	896
8	4763	3584	4480	3584	4096	4096	4096	4096	4608	3584	4608	3584
9	17536	15360	17536	15360	17536	15360	17536	15360	17536	15360	17536	15360
10	65792	65280	65280	65792	69632	61440	69632	61440	65792	65792	65280	65280

Examples:

S(2;0,3) = 2 = |{13,31}| and S(3;0,0) = |{000,022,202,220}|.

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;t,s) = 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)
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?

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 1554 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.