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/13: pages 61-63/17, 10 (15 pts), 28a.
• Due on 09/20: page 62/13 (15 pts), page 65/37 (15 pts), page 67/61 (15 pts).
• Due on 09/27: p.83/9--first question (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?); p.84/14; p.83-84/20 (hint: recall the proof in class for K_6 - - > K_3,K_3).
• Due on 10/4: p.119/10 (also write the permutations as products of adjacent transpositions).
• Due on 10/11: p.119/7,9. Hint: to determine the permutations with one less inversion than the maximum, use the map w --> reverse permutation w' (read entries from right to left), and the fact (not hard to prove) that inv(w)+inv(w')=n(n-1)/2.
• Due on 10/18: p.155-156/12,18; page 158/30.
• Due on 10/25: page 159/40,43. Hint for 43: use induction; namely, take the expansion of 1/(1-x)^n and use either: (1) multiplication by 1/(1-x)=1+x+x^2+... OR (2) a derivative.
• Due on 11/1: page 201/32; p. 263/48e, via both characteristic polynomial and generating functions.
• Due on 11/15: p. 316/3; p. 317/12d; compute the Stirling numbers S(7,k) for all k (Hint: use exercise 317/12 for the easier ones).
• Due on 11/27:
  • 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/6: 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).
• Practice problems on network flows and matchings:
  • page 535-536/24
  • page 337/6 (use the flow algorithm in the associated network).

• combinations/permutations with/without repetition
• (generalized) pigeonhole principle
• binomial formula and its generalizations (multinomial, Newton)
• recurrence relations (via characteristic polynomial and generating functions)
• inclusion-exclusion principle (including applications to combinations with repetition)
• bijections between objects counted by Catalan numbers, Stirling numbers of the second kind
• trees (especially equivalent definitions)
• network flows and application to matchings.