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 4-ary word is the sum of its digits mod 4, i.e. 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, i.e. s = SUM( a_ia_j : 1 < i < j < n ).

Examples:

• The two 4-ary strings of trace 0, subtrace 3 and length 2 are { 13, 31 }.
• The four 4-ary strings of trace 0, subtrace 0 and length 3 are { 000, 022, 202, 220 }.
• The four 4-ary strings of trace 2, subtrace 0 and length 3 are { 002, 020, 200, 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,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?

• Each column is a sequence whose ordinary generating function is rational with denominator
  D = (4z-1)(8z²-4z+1)(16z⁴+1)(2z-1).

• Column (0,0) is sequence A073953 in Neil J. Sloane's database of integer sequences. The numerator of the ogf is 1 -9z +32z² -56z³ +48z⁴ -104z⁵ +352z⁶ -576z⁷ +320z⁸.
• Column (0,1),(2,3) is sequence A068711 in Neil J. Sloane's database of integer sequences.
• Column (0,2) is sequence A073955 in Neil J. Sloane's database of integer sequences.
• Column (0,3),(2,1) is sequence A068777 in Neil J. Sloane's database of integer sequences.
• Column (1,0),(3,0) is sequence A068786 in Neil J. Sloane's database of integer sequences.
• Column (1,1),(3,1) is sequence A068778 in Neil J. Sloane's database of integer sequences.
• Column (1,2),(3,2) is sequence A073959 in Neil J. Sloane's database of integer sequences.
• Column (1,3),(3,3) is sequence A068788 in Neil J. Sloane's database of integer sequences.
• Column (2,0) is sequence A068789 in Neil J. Sloane's database of integer sequences.
• Column (2,2) is sequence A073962 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:12:35 PDT.
There have been 992 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.