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/12: p.62-63/17, 20
• Due on 09/19: p.61-67/10 (15 pts), 28a, 13 (15 pts), 37 (15 pts), 61 (15 pts).
• Due on 09/29: p.83-84/9-first question (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, 20 (hint: recall the upper bound proof in class)
• Due on 10/03: p.119/9,10 (in #10, also write the permutations as products of adjacent transpositions)
• Due on 10/10: p.119/7 and p.155-156/12,18.
• Due on 10/17: 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/24: p.159/40,43; p.201/32; p. 198/6
• Due on 10/31: p.199/11, p.259/17, p. 263/48d,e via characteristic polynomial (10 pts each)
• Due on 11/7:
  • 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.
  • use generating functions to find a_n given by a_n= - 6 a_{n-1} - 9 a_{n-2}, a_0=1, a_1= - 4.
• Due on 11/14: p.315-317/1 (Hint: construct a bijection to ballot sequences), 4b, 13, 14 for p=4 only
• Due on 11/21:
  • page 317/12d
  • compute the Stirling numbers S(7,k) for all k (Hint: use exercise 317/12 for the easier ones) and then the Bell number B_7
  • 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)
• Due on 12/1:
  • page 453/29
  • 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).
  • 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; do not forget to prove both implications).
• Due on 12/8:
  • page 535-536/24--only the last two networks in fig. 13.16 (10 pts each)
  • (15 pts) Prove the following generalization of Hall's theorem: the size of the max matching rho(G) in an arbitrary bipartite graph G=(X,Y) is |X|-d(G), where d(G)>=0, called the defect of G, is the maximum of |A|-|Delta(A)|, over all subsets A of X (including the empty one). Hint: Use rho(G)=c(G). First show that c(G)<=|X|-d(G), by letting A be such that |A|-|Delta(A)| is maximum, so equal to d(G), and by then showing that "Delta(A) U (X\A)" is an edge cover. Then show that c(G)>=|X|-d(G) by complete analogy with the main part of the proof of Hall's theorem in class.
  • page 337/6 (use the flow algorithm in the associated network).