Here we consider the set S(n;t,s) of length n words a₁a₂···a_n over the alphabet consisting of the elements of the field F₂ that have trace t and subtrace s. The trace of a word is the sum of its digits over the field F₂ , i.e. t = a₁+a₂+ ··· +a_n. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken over the field F₂ , i.e. s = SUM( a_ia_j : 1 < i < j < n ). Note that F₂ = Z₂ .

Examples:

• The two binary strings of trace 1, subtrace 0 and length 2 are { 10, 01 }.
• The three binary strings of trace 0, subtrace 1 and length 3 are { 011, 101, 110 }.
• The four binary strings of trace 1, subtrace 1 and length 4 are { 0111, 1011, 1101, 1110 }.

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,s) + S(n-1;t+1,s+t+1)

  Note that all operations involving operands t or s are carried out over GF(2).

• Column (0,0) is sequence A038503 in Neil J. Sloane's database of integer sequences.
• Column (0,1) is sequence A038505 in Neil J. Sloane's database of integer sequences.
• Column (1,0) is sequence A038504 in Neil J. Sloane's database of integer sequences.
• Column (1,1) is sequence A00749 in Neil J. Sloane's database of integer sequences.

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:13 PDT.
There have been 1154 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.