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/07: pages 61-63/17, 20.
• Due on 09/14: pages 61-63/10 (15 pts), 28a.
• Due on 09/26: page 62/13 (15 pts), page 65/37 (15 pts).
• Due on 09/28: page 67/61 (15 pts); 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.
• Due on 10/5: p.83-84/20 (hint: recall the proof in class for K_6 - - > K_3,K_3).
• Due on 10/24: p.119/10 (in #10, also write the permutations as products of adjacent transpositions); p.155-156/12,18.
• Due on 10/26: 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/2: page 201/32; page 198/6; p. 263/48d,e via characteristic polynomial.
• Due on 11/9: 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/28: 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/30:
  • 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/7:
  • 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).
  • show that if a tree has a vertex of degree 3, it must have at least 3 leaves (note that this is immediate based on the statement in class describing all trees with precisely 2 leaves); then describe the trees with precisely 3 leaves. Hint: you could extend to this case the proof in class related to trees with 2 leaves, based on "sum d_i=2(n-1)" (for a tree with n vertices); see also the book for this proof.
• 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.