Math 386: Combinatorics Homework Assignments V - VIII

Fall 2006

HOMEWORK V (9/29)

Read for Wed., 10/4: Sects. 5.1, 5.2.

Do for discussion on
Thurs., 10/5: Ch. 5, ## 1-5, 7, 15, 16, 23(a,b), and A2.
Fri., 10/6: Ch. 5, ## 8, 18, 23(c), 24, and A1.

Hand in Mon., 10/9: Ch. 5, ## 6, 9, 23(d).

Problem Set A

• A1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 (m choose 2) + (m choose 1).
• A2. Prove combinatorially that (n choose k) = (n choose n-k) for n ≥ k ≥ 0.

HOMEWORK VI (10/6,12)

Read for Mon., 10/9: Sects. 5.3, 5.6 (omit p. 150).

Do for discussion on
Thurs., 10/12: Ch. 5, ## 13, 19, 21, 22, and B1, B2(a-l).
Fri., 10/13: Ch. 5, ## 17, 18, 20, and B1(again), B2(m-p), B3. In #18, don't use the integrated binomial theorem. In #20, simplify your answer as far as you can.

Hand in Mon., 10/16: Ch. 5, ## 10, 11, 14, and B2(q-t), B4, B5. In #14, don't assume k ≤ r.

Problem Set B

• B1. Give a combinatorial proof of Chapter 5, #13.
• B2. Evaluate (that means, as an actual number) the following binomial coefficients. Feel free to look for patterns.
  1. (5 choose 4)
  2. (4 choose 5)
  3. (5.6 choose 2)
  4. (0 choose 0)
  5. (0 choose 7)
  6. (7 choose −1)
  7. (0 choose −1)
  8. (−1 choose 0)
  9. (−1 choose 1)
  10. (−1 choose 2)
  11. (−1 choose 3)
  12. (−1 choose 4)
  13. (1/2 choose 0)
  14. (1/2 choose 1)
  15. (1/2 choose 2)
  16. (1/2 choose 3)
  17. (−1/2 choose 0)
  18. (−1/2 choose 1)
  19. (−1/2 choose 2)
  20. (−1/2 choose 3)
• B3. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or #B1 or Pascal's formula might suggest an idea.)
• B4. Give a combinatorial proof of the first equation in Ch. 5, #7.
• B5. Prove Ch. 5, #22 combinatorially, assuming r, m, k are integers and r ≥ m ≥ k ≥ 0 (that's r >= m >= k >= 0, if your browser doesn't do ≥).

HOMEWORK VII (10/12-13)

Read for Mon., 10/16: Sects. 5.4, 5.5.

Do for discussion on
Thurs., 10/19: Ch. 5, ## 17, 25, 31, 35 (for n = 2,3,4), 36, 38, 40.
Fri., 10/20: Ch. 5, ## 23, 32, 34, 35 (for n = 5), 42, and C2.

Hand in Mon., 10/23:
Ch. 5, ## 33, 35 (for all n), 41, and C1, C3.

Problem Set C

• C1. Let S_n = {1,2,...,n}. Construct a partition of the combinations of S₆ into symmetric chains. Use your solution of #34 as a starting point and apply the method of the book.
• C2. Find (and prove, if you can) a simple formula for (-1 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-x).
• C3. Find (and prove, if you can) a simple formula for (-2 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-x)².

HOMEWORK VIII (10/13-16)

Do for discussion on
Mon., 10/23: # D1, D3.
Wed., 10/25: # D2.

Problem Set D

• D1. Find (and prove, if you can) a (relatively) simple formula for (-1/2 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-4x)^1/2.
• D2. Find (and prove, if you can) a (relatively) simple formula for (1/2 choose n), n ≥ 1. Use your formula to find a simple power series expansion of (1-4x)^1/2.
• D3. Here are two simple problems in extremal set theory, different from the one that Sperner's Theorem solves. These won't be on the test but they're interesting and you might like to take a look at them.
  1. What is the largest number of combinations of an n-element set that can be chosen, so that any two chosen combinations have empty intersection?
  2. What is the largest number of combinations of an n-element set that can be chosen, so that no two chosen combinations have empty intersection?

TEST II is on Thursday, Oct. 26!