MATH 357 – Combinatorics Review Sheet for Final Exam May 1, 2017

General Information and Groundrules

The final exam in Combinatorics this semester (for those not doing a final project) will be given at the announced time for MWF 11am classes – Friday, May 12 at 11:30am in Swords 302. This will be a closed-book, individual exam. No use of phones, I-pods, tablets, or any other electronic devices beyond a calculator will be allowed during the exam – turn them off and stow them in your backpack.

What might be covered

The exam will be comprehensive – it will cover all of the material we have discussed from Chapters 1 - 8 of Beeler. I will write the exam so that it should take about 100 minutes (twice the regular class hour) to complete if you are well-prepared and work steadily. However, you will have the full 150 minutes (11:30am - 2:00pm) to work on the exam if you need the time. In addition, there might be a question dealing with material from some of the final project presentations. The set-up will be similar to the midterms; you will have the choice to omit some questions and still earn 100 out of 100 points.

Specifically the topics are:

1) Mathematical sets, unions, intersections, functions, etc.

2) The Multiplication and Addition Principles

3) The Pigeonhole Principle (basic and generalized versions)

4) Permutations, cycle decompositions, counting permutations by cycle type or cycle index, the Stirling numbers of the first kind (Know the proof of the recurrence relation s(n + 1, k) = ns(n, k) + s(n, k − 1).)

5) Legendre’s theorem on divisiblity of n! by a primes p.

6) Numbers of permutations P (n, k) and binomial coefficients \binom{n}{k} and the counting problems they solve.

7) Poker hands and related counting problems

8) Binomial coefficient identities – know algebraic and combinatorial proofs of the “Vandermonde convolution identity” identity (Theorem 3.4.4)

\binom{n + m}{k} = ∑_{i=0}^{k} \binom{n}{i}\binom{m}{k − i}.

9) Multinomial coefficients.

10) The different categories of distribution problems and the counting techniques needed for them. This is basically the material appearing in Table 4.6 on page 109 of Beeler. You should know the formulas in the first two columns there and be able to analyze a problem to determine which one applies. Note that this includes a) The “stars and bars” or dividers idea for the unlabeled balls, labeled urns case b) Partitions of an integer into a fixed number of parts and into any number of parts.

Know the recurrence relation for p(n, k) and its proof.

c) The Stirling numbers of the second kind. Know the recurrence relation for S(n, k) and its proof.

11) Single- and Multivariable generating function techniques for counting problems. Note that you won’t have Maple to use on the exam, so I might ask questions about how problems would be set up and what you would be looking for in the generating function without asking for a single number answer. There are some examples in the Review Problems below.

12) Finding recurrence relations for sequences from counting problems. Know in particular the recurrences D_{n} = (n − 1)D_{n−1} + (n − 1)D_{n−2} and D_{n} = nD_{n−1} + (−1)^{n} for the number of derangements of [n] and how they are proved.

13) Generating functions and recurrences. Solving constant-coefficient linear recurrences in the homogeneous and inhomogeneous cases. The relation between the generating function methods and the “shortcuts” based on the characteristic polynomial of the recurrence. If I ask you to solve an inhomogeneous recurrence, I would give you the Table 6.1 on p. 185 containing the “good guesses” for the particular solution.

14) The general Inclusion-Exclusion Principle. Know the statement, the proof by induction on the number of sets in the union, and how to apply it.

15) Group actions, Burnside’s Lemma – Theorem 8.3.1 – (know the statement and the proof), Burnside for Colorings, Polya’s Enumeration Theorem – 8.5.3 (know how to apply it; I wouldn’t ask for a proof here because we did not do one in detail).

How to Prepare

Start by reviewing your class notes, problem sets, and exams. Pay special attention to anything you did not “get” before and be sure you understand the posted solutions and how to attack similar problems. Then, try some or all of the following review problems. I will post solutions for these about a week before the exam.

Review Problems

Disclaimer: These problems are only intended to give you an idea of the range of topics and to help you review the concepts. The actual exam questions will not be exactly like these. This list is also quite a bit longer than the actual exam will be.

From Beeler: 1.3.13, 1.4.8, 1.5.7, 2.1.22, 2.2.9, 2.3.9, 2.4.8, 2.5.9, 2.7.15, 3.1.15, 3.2.7, 3.3.8, 3.5.6, 3.6.20, 4.2.12, 4.2.19, 4.3.14, 4.3.15, 5.3.9 (just say how you would solve this using a generating function), 5.4.9 (same directions), 6.1.20 (figure 6.2 is at the top of the page), 6.3.10 (solve with a generating function and by the “shortcut” method), 6.5.27, 7.1.16 (just say how you would solve it using generating functions), 7.3.4, 8.3.20, 8.5.12 (just say how you would solve it using the Polya Theorem).