Math 328 - Combinatorics: Syllabus and Homework

Syllabus

Textbook for assignments: Richard Brualdi, Introductory Combinatorics, 5th edition.

All problems are worth 10 points unless otherwise specified.

• Due on 09/09: pages 61-63/17, 20, 10 (15 pts), 28a.
• Due on 09/16: page 62/13 (15 pts), page 65/37 (15 pts).
• Due on 09/23: page 67/61 (15 pts); p.83-84/9 (15 pts.; hint: what can the sums of ages possibly be? what are the balls and boxes, if we want two groups with the same age sum?), 14; p.83-84/20 (hint: recall the proof in class for K_6-->K_3,K_3).
• Due on 09/30: p.119/7,9,10 (in #10, also write the permutations as products of adjacent transpositions); p.155-156/12,18.
• Due on 10/7: p.158/30 Hint: reduce to Sperner's theorem (maximum size of an antichain) for {1,2,3}; namely, pick a "bad" element in the antichain for {1,2,3,4} and show that this forces its size to be strictly less than 6.
• Due on 10/14: page 159/40,43;
• Due on 10/21: page 201/32; page 198/6.
• Due on 10/28: page 259/17, p. 263/48d,e via characteristic polynomial.
• Due on 11/11: use generating functions to find a_n given by the recurrence a_n=4 a_{n-1} - 3 a_{n-2}, a_0=2, a_1=5; a_n= - 6 a_{n-1} - 9 a_{n-2}, a_0=1, a_1= - 4. (10 pts each)
• Due on 11/7: p. 315-316/1 (Hint: construct a bijection to ballot sequences), 3.
• Due on 11/18:
  • page 317/12d, 14 for p=4 only
  • compute the Stirling numbers S(7,k) for all k (Hint: use exercise 317/12 for the easier ones).
• Due on 11/28:
  • show that p(n) is smaller than p(n+1) for every n (Hint: construct an appropriate one-to-one map)
  • page 318/29 (you can ignore the remark; hint: use a statement proved in class about partitions with bounded parts).
• Due on 12/2: page 453/29.
• Due on 12/9: show that T is a tree if and only if it has no cycles, but by adding any non-existing edge we get a cycle (pick the most appropriate characterization of a tree, among those given in class and the book; do not forget to prove both implications).
• Due on 12/12: show that if a tree has a vertex of degree 3, it must have at least 3 leaves (10 points); describe the trees with precisely 3 leaves (10 points). Hint: you could extend to this case the proof in class that every tree has at least 2 leaves, based on "sum d_i=2(n-1)" (for a tree with n vertices); see also the book for this proof.