Some problems (best viewed with Netscape 2 or other
browser that supports subscripts and superscripts):
-
Prove that na - 1/3 a3 - 1/2 a2
- 1/6 a is integer for all integers a.
Due: January 31.
-
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.
-
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.
-
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.
-
Solve the recurrence relation
t(n,1) = 1
t(n,k) =
1 + sum( t(j,k-1), j=0..n );
Due: March 5.
-
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.
-
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.
-
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]
-
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]
-
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:
-
How many extended binary trees are there of maximum diameter?
[5 marks]
-
Derive a simple recurrence relation for E(n,k), the number of alternating
permutations p for which p[1] = k. A permuation is alternating
if p[1] < p[2] > p[3] < p[4] ... [10 marks]