Mathematics 357 – Combinatorics Review Sheet for Midterm Exam 2 April 8, 2005

General Information

As announced in the course syllabus and on the course homepage, the second midterm exam will be given in class on Friday, April 15. The exam will cover the material we have studied since the first exam, through the material on general graphs from the start of Chapter 11 from classes April 6 and 8. (This includes sections from Chapters 6,7,9,11 in the text – see detailed list of topics you are responsible for below). Important Note: Much of this material makes use of the basic counting techniques we learned earlier. So there may be parts of questions that deal with material from the first exam too(!) Be prepared.

This will be an individual, closed-book, closed-notes exam. No collaboration of any kind will be permitted during the exam period. You may bring a calculator if you want one; however, answers written terms of powers, factorials, binomial coefficients, etc. can always be left in that form, so a calculator should be of truly minimal value for your work on the exam. My advice: leave it home!

If there is interest, I would be happy to run a late afternoon or evening review session next week to help you prepare. Wednesday evening after the πμϵ induction and majors’ dinner will be OK if that’s a good time for you.

Topics to be Covered

1) Chapter 6: Inclusion-Exclusion Principle in the “union” and “complement of union” forms. Applications to counting combinations with repetition, derangements, permutations with forbidden positions (“rook placement” problems). Also know how to compute and use rook polynomials for these counting problems, including the product and expansion rules. (Omit section 6.6.)

2) Chapter 7: Number sequences, recurrences, solving homogeneous and nonhomogeneous linear recurrences with constant coefficients. Generating functions, and the generating function technique for solving recurrences. (Omit section 7.7)

3) Chapter 9: Hall’s “Marriage Theorem”, matchings in bipartite graphs, applications. (Note: you are only responsible for the topics here we covered in class. There’s actually a lot more in Chapter 9 than we looked at, and it’s presented differently in some cases. So my advice is: use the class notes!)

5) Chapter 11: Terminology and basic concepts for graphs and multigraphs (section 11.1 only on this exam).

Proofs to know

• The proof of the formula

D_{n} = n! (1 − \frac{1}{1!} + \frac{1}{2!} + ⋯ + \frac{(−1)^{n}}{n!} )

for the derangement number D_{n}. (See Theorem 6.3.1 in the text and the class notes.)

• The proof of Hall’s “Marriage” Theorem (as we did it in class, not the book’s approach).

Some Good Practice Problems

• Chapter 6/2, 8, 11, 14, questions like 24 (Suggestion: make up your own 5 × 5 or 6 × 6 boards to practice and also compute the rook polynomials in addition to finding the number of placements of n non-attacking rooks on the unshaded squares via Theorem 6.4.1.), 26

• Chapter 7/3, 5, 9, 14, 24, 27, 28, 29, 30 d,e, 34, 36

• Chapter 9/9, 12, 16, 27

• Chapter 11/3,4,5,6,8

Warning: The above problems cover the ideas you will need to understand in order to do the exam problems, but the exam problems may be organized and formatted differently, may draw on different types of examples, etc. Be prepared!