Some problems (best viewed with Netscape 2 or other browser that supports subscripts and superscripts):

  1. Prove that na - 1/3 a3 - 1/2 a2 - 1/6 a is integer for all integers a.
    Due: January 31.
  2. Find two natural numbers x and y such that that gcd(x+i,y+j) > 1 for all 0 <= i <= 3,0 <= j <= 3?
    Due: February 14.
  3. Complete the proof that Nk(n) = 1/n sum( totient(n/d)*kd, d in divisors(n) ), starting from the equation Nk(n) = sum( Lk(d), d in divisors(n) ). This is the proof we started in class.
    Due: February 14.
  4. How many circular binary strings of length n are there with no substring 00? How many of them are aperiodic? How many length n necklaces are there with r white beads and n-r black beads?
    Due: February 28.
  5. Solve the recurrence relation
    t(n,1) = 1
    t(n,k) = 1 + sum( t(j,k-1), j=0..n );
    Due: March 5.
  6. Run the LHS of (7.11) from "Combinatorial Identities" by H.W. Gould through Maple, and explain how to get from Maple's answer to the RHS of (7.11). Recall that the LHS of (7.11) is sum[ (-1)^k C(n,k) C(x+k,k) 2^{2k} / C(2k,k) / (x+k) ] where the sum is over k=0..n, and where C(n,r) is the binomial coefficient n choose r. You need to get the RHS expressed in terms of binomial coefficients with no fractional parameters. I.e., it's ok to have one binomial coefficient dividing another, but no coefficient should have the form C( a, b ) where a is a fraction.
    Due: March 5.
  7. How many red-black trees are there with 100 leaves? (HINT: Derive a recurrence relation and then use Maple.) For more explanation of red-black trees see http://sue.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.
    Due: March 13.
  8. What is the sum over all extended binary trees of n internal nodes of the lengths of the paths between every pair of leaves? Between every pair of internal nodes? (Hint: Use generating functions)
    Due: March 20. [40 marks]
  9. Prove that sum( S(n,k)*x^n, n ) = x^k/[(1-x)(1-2x)...(1-kx)], where S(n,k) is a Stirling number of the second kind.
    Due: March 27. [30 marks]
  10. For fixed k, what is the asymptotic value of sum( sum( ki/i, i=1..j), j=1..n ).
    Due: April 3 (last day of class). [40 marks]
Extra Problems: