MATH 357 – Combinatorics Review Sheet for Exam 2 March 30, 2017

General Information and Groundrules

The second midterm exam in Combinatorics this semester will be given (as announced in the course syllabus) in class on Friday, April 7. This will be a closed-book, individual exam. You may use a basic calculator if you like.

What might be covered

The new material on this exam will be the topics we have studied since Exam 1 (the material from problem sets 4,5,6,7). In Beeler, this covers Chapters 4 (Distribution Problems), Chapter 5 (Generating Functions) and Chapter 6 (Recurrences). We did not really discuss §§4.4 or 6.4, so nothing from them will be included.

Important Note: Many of the techniques in Chapter 4 rely on things done earlier. So facts about binomial or multinomial coefficients, permutations, etc. may also enter into the questions on this exam.

Specifically the new topics are:

1) 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.

2) Algebraic techniques for factoring polynomials in the form

(1 − c_{1}x)(1 − c_{2}x) ⋯ (1 − c_{k}x)

and the relation of c_{i} to the roots of the polynomial

3) Geometric series expansions; consequences obtained by substitution, differentiation, etc.

4) 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. That’s what questions IV and V below mean(!)

5) 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.

6) Generating functions and recurrences

7) 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.

Some review/practice 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 and some of the ways I am asking things here would not be appropriate for an exam question. This list is also quite a bit longer than the actual exam will be.

I. Find the number of distributions of 5 balls into 3 urns in each of the following cases. For all parts of the question,

(i) give the number of distributions as a case of the formulas from Table 4.6, then (ii) evaluate the number to a single integer using recurrences, etc., then (iii) describe what the distributions you are counting actually mean (e.g. by listing what those distributions actually do to the balls). Note: it will be tedious to list every possible case for some of these – you can stop when you are tired if the pattern is clear; the point of the question is to make sure you really understand what the number from item ii means(!)

A) Both the balls and the urns are labeled B) Same as 1, but no urn is empty C) The balls are labeled, but the urns are not labeled D) Same as 3, but no urn is empty E) The urns are labeled, but the balls are not labeled F) Same as 4, but no urn is empty

II. Give a combinatorial proof of the recurrence

S(n, k) = ∑_{i=1}^{n} S(n − i, k − 1)k^{i−1}.

(Hint: Think about the way the “one-step” recurrence from Theorem 4.3.8 is proved, but “keep going.”)

III. How many different ways are there to distribute 20 boiled eggs (say all from jumbo white-shell eggs with no flaws, no cracks, ... ) to 10 children? How many if every child gets at least one egg? How many if the eggs have been decorated for Easter with 20 different colors or patterns?

IV. Give a “generating function recipe” (see point 4 in the list of topics covered if you don’t know what this means) for counting the number of unordered 12-letter words from the alphabet V, W, X, Y, Z that satisfy all of the following:

(i) If V is used, then it is used exactly 3 times (ii) W is used an even number of times (possibly 0 times) (iii) X is used at least 4 times (iv) Y appears no more than 2 times

(v) Z appears the same number of times that Y does. (You’ll need to think about this one; it’s not exactly like anything we did before but you should see what to do if you think about it the right way(!))

V. Give a “generating function recipe” (see point 4 in the list of topics covered if you don’t know what this means) for finding the number of vectors (x_{1}, x_{2}, x_{3}, x_{4}) of non-negative integers that satisfy:

\begin{aligned}3x_{1} + 4x_{2} + 5x_{3} + 2x_{4} & = 20 \\ 2x_{1} + 2x_{2} + 3x_{3} + 3x_{4} & = 18 \end{aligned}

What would change if the second = was replaced by ≤?

VI. Using any appropriate method, determine the number of derangements of [7] (that is, the number D_{7}). What fraction of the elements of S_{7} are derangements?

VII. Recurrences. A) Show directly (i.e. without solving the recurrence) that R_{n} = 6^{n} satisfies R_{n} =

7R_{n−1} − 6R_{n−2}, and R_{0} = 1, R_{1} = 6. B) Solve the following homogeneous recurrence using the generating function method:

R_{n} = 7R_{n−1} − 12R_{n−2}

with initial conditions R_{0} = 1 and R_{1} = 0. C) What would the general solution of a homogeneous recurrence with characteristic

polynomial

(1 − 4x)^{4}(1 − 5x)^{3}(1 − 6x)

look like? D) Solve the following inhomogeneous recurrence using our “shortcut” method and un-

determined coefficients:

R_{n} = 7R_{n−1} − 12R_{n−2} + n^{2}

with initial conditions R_{0} = 1 and R_{1} = 0. (Note: The associated homogeneous recurrence is the same as the one in part B.)

E) Solve the following inhomogeneous recurrence using our “shortcut” method and un-

determined coefficients:

R_{n} = 7R_{n−1} − 12R_{n−2} + 4^{n}

with initial conditions R_{0} = 1 and R_{1} = 0. (Note: The associated homogeneous recurrence is the same as the one in part B.)