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

Examples:

• The two binary strings of trace 0, subtrace 0 and length 4 are { 0000, 1111 }.
• 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))

• Column (0,0) is sequence A038503 in Neil J. Sloane's database of integer sequences.
  The value is ( ⁿ₀ ) + ( ⁿ₄ ) + ( ⁿ₈ ) + ··· ,
  which has the closed form expression ( 2ⁿ + (1+i)ⁿ + (1-i)ⁿ )/4, where i is the square root of -1.
  The i can be eliminated to get ( 2ⁿ + 2 sqrt(2)ⁿ cos( Pi.n/4 )/4.
  The sequence has the rational generating function (1-x)³/((1-x)⁴-x⁴).
  

• Column (0,1) is sequence A038505 in Neil J. Sloane's database of integer sequences.
  The value is ( ⁿ₂ ) + ( ⁿ₆ ) + ( ⁿ₁₀ ) + ··· ,
  which has the closed form expression ( 2ⁿ - (1+i)ⁿ - (1-i)ⁿ )/4, where i is the square root of -1.
  The i can be eliminated to get ( 2ⁿ - 2 sqrt(2)ⁿ cos( Pi.n/4 )/4.
  The sequence has the rational generating function x²(1-x)/((1-x)⁴-x⁴).
  

• Column (1,0) is sequence A038504 in Neil J. Sloane's database of integer sequences.
  The value is ( ⁿ₁ ) + ( ⁿ₅ ) + ( ⁿ₉ ) + ··· ,
  which has the closed form expression ( 2ⁿ - i(1+i)ⁿ) + i(1-i)ⁿ )/4, where i is the square root of -1.
  The i can be eliminated to get ( 2ⁿ + 2 sqrt(2)ⁿ sin( Pi.n/4 )/4.
  The sequence has the rational generating function x(1-x)²/((1-x)⁴-x⁴).
  

• Column (1,1) is sequence A00749 in Neil J. Sloane's database of integer sequences.
  The value is ( ⁿ₃ ) + ( ⁿ₇ ) + ( ⁿ₁₁ ) + ··· ,
  which has the closed form expression ( 2ⁿ + i(1+i)ⁿ) - i(1-i)ⁿ )/4, where i is the square root of -1.
  The i can be eliminated to get ( 2ⁿ - 2 sqrt(2)ⁿ sin( Pi.n/4 )/4.
  The sequence has the rational generating function x³/((1-x)⁴-x⁴).
  

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 1127 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.