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/10: p.61-63/17, 20, 10 (15 pts), 28a, 13 (15 pts).
• Due on 09/17: p.65-67/37 (15 pts), 61 (15 pts); p.83-84/9-first question only (hint: what can the sums of ages possibly be? you can assume no two people have the same age. what are the balls and boxes, if we want two groups with the same age sum?), 14.
• Due on 10/06: p.83-84/20 (hint: recall the upper bound proof in class)
• Due on 10/08: p.119/9,10 (in #10, also write the permutations as products of adjacent transpositions)
• Due on 10/15: p.119/7 and p.155-156/12,18.
• Due on 10/29: 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; p.159/40,43; p.201/32.
• Due on 11/5: p. 198/6; p.259/17 (optional), p. 263/48d,e via characteristic polynomial; 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/12: p. 315-316/1 (Hint: construct a bijection to ballot sequences), 3.
• Due on 11/19:
  • 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 12/1:
  • 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); page 453/29.
• Due on 12/3:
  • show that if a tree has a vertex of degree 3, it must have at least 3 leaves; describe the trees with precisely 3 leaves. 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.
  • 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 by 12/11 in my mailbox (drop in the Math office):
  • page 535-536/24--only the last two networks in fig. 13.16 (10 pts each)
  • page 337/6 (use the flow algorithm in the associated network).