CSC 482/582 SUMMER 2012 Assignment #4 Due June 13 by midnight. 1. Formulate and prove the "hexagon property" mentioned on page 155 in the text. 2. Find a formula for the number of length n binary necklaces that do not have any substring 00. Do the same for the number of aperiodic binary necklaces. You will find it useful to first determine the number of length n binary strings with no substring 00. 3. Evaluate SUM( (-1)^{n-j} binomial(n,j) (k+j)^n, j = 0..n ). Remarkably, you get the same answer no matter the value of k. NOTE: If you are stuck try a proof by induction on n; make use of some of the identities early in Section 5.1. 4. Show that if 0 < j < k < n then GCD( BINOMIAL(n,j), BINOMIAL(n,k) ) > 1. If you are stuck, try to make use of (5.21). 5. Use Maple or Sage to find the inverse of the matrix whose (n,k) entry is T[n,k] = k/(2n-k)BINOMIAL(2n-k,n-k) for n = 7. On the basis of what you observe, make a conjecture about what the entries of the inverse are, and prove that your conjecture is correct. Note: You may find the following identity to be useful: k/(2n-k)BINOMIAL(2n-k,n-k) = BINOMIAL(2n-k,n-k)-2*BINOMIAL(2n-k-1,n-k-1). QUIZ PRACTICE QUESTIONS (not to turn in) - Prove that n | BINOMIAL(n,k) for all 0 < k < n if and only if n is prime. ANSWER: See the second paragraph on the right-hand side on page 1 of http://webhome.cs.uvic.ca/~ruskey/Publications/VennNAMS/fea-wagon.pdf - Prove that SUM( k FLOOR(n/k), k = 1..n ) = SUM( sigma(k), k = 1..n ) where sigma(n) is the sum of the divisors of n. This is the same sigma that appeared on the last quiz.