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).
Topics for the final exam:
- 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.
Cristian Lenart, Department of Mathematics,
ES 116A,
SUNY at Albany