MATH 357 – Combinatorics Solutions for Review/Practice Problems on Review Sheet for Exam 2 March 31, 2017

Some review/practice problems

Disclaimer: These problems are only intended to give you an idea of the range of topics on the exam 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 Solution: (i) The number is 3^{5} (ii) This equals 243. (iii) The number here represents all ways to split up the 5 balls into 3 subsets, with no limitations on the sizes of the subsets. So for instance there are the cases where all the balls go in one urn (3 of those). Then cases where the 4 of the balls go in one urn and one goes in one of the other urns (and the last urn is empty), e.g. ({1, 2, 3, 4}, {5}, {}) (3 · 2 · 5 = 30) of these. Then cases where three of the balls go in one urn and two go in one of the others (3 · 2 · 10 = 60 of these. Then cases where three of the balls go in one urn and the other two are split between the other urns (3 · 10 · 2 = 60 of those). Then cases where there are two balls in one urn, two in a second, and 1 in the last (3 · 5 · 3 = 90 of those).

B) Same as 1, but no urn is empty Solution: (i) The number is 3!S(5, 3). (ii) Using the recurrence relation for the Stirling numbers of the second kind, this equals

6S(5, 3) = 6 · (3S(4, 3) + S(4, 2)) = 18(3S(3, 3) + S(3, 2)) + 12S(3, 2) + 6S(3, 1)

Recall that S(n, k) is the number of ways to place n labeled balls into k unlabeled urns so that no urn is empty. Hence S(3, 3) is clearly equal to 1 – each urn gets one ball. Similarly S(3, 1) = 1 since all three balls must go in the single urn. Finally S(3, 2) = 3 since one of the two urns must get two of the balls and there are \binom{3}{2} = 3 different ways to choose the two balls that end up in that urn. Hence the total number here is 18 · (3 + 3) + 12 · 3 + 6 = 150. (iii) You are counting the cases in A where the distribution is 3, 1, 1 or 2, 2, 1 (no urn empty). Hence the number is the 60+90 = 150.

C) The balls are labeled, but the urns are not labeled Solution: (i) The number is S(5, 3) + S(5, 2) + S(5, 1). (ii) From the calculations in part A, we can see S(5, 3) = 25 (divide the answer there by the 6 = 3!). Using the recurrence relation in the same way,

S(5, 2) = 2S(4, 2) + S(4, 1) = 2(2S(3, 2) + S(3, 1)) + S(4, 1) = 4 · 3 + 2 · 1 + 1 = 15.

Finally S(5, 1) = 1. Hence the total is 25 + 15 + 1 = 41. (iii) The S(5, 1) counts cases where all the balls go in one urn. Since the urns are unlabeled that can happen only in one way – {{1, 2, 3, 4, 5}, {}, {}}. The S(5, 2) counts cases where the balls go into two of the urns. But the balls are labeled, so it matters which balls go where. {{1, 2, 3, 4}, {5}, {}}, {1, 2, 3, 5}, {4}, {}}, (5 of these altogeher), then \{\{1, 2, 3\}, \{4, 5\}, \{, \}\}, etc. (\binom{5}{3} = \binom{5}{2} = 10 of these). Then the S(5, 3) counts the number of distributions where no urn is empty. There are “3,1,1” (10 of these) and “2,2,1” distributions (5 · 3 = 15) of these.

D) Same as 3, but no urn is empty Solution: (i) S(5, 3). (ii) = 25. (iii) Take the cases from C where no urn is empty (the numbers are all nonzero).

E) The urns are labeled, but the balls are not labeled Solution: (i) The number is \binom{n+k−1}{k−1} = \binom{7}{2}. (ii) This is \frac{7·6}{2} = 21. (iii) You can count these by listing the vectors (x, y, z) where x, y, z ≥ 0 are integers (the numbers of balls in each urn) and x + y + z = 5:

(5, 0, 0), (4, 1, 0), (4, 0, 1), (3, 2, 0), (3, 1, 1), (3, 0, 2), (2, 3, 0), (2, 2, 1),
(2, 1, 2), (2, 0, 3), (1, 4, 0), (1, 3, 1), (1, 2, 2), (1, 1, 3), (1, 0, 4), (0, 5, 0),
(0, 4, 1), (0, 3, 2), (0, 2, 3), (0, 1, 4), (0, 0, 5).

(Note: 21 vectors!) F) Same as 4, but no urn is empty.

Solution: The number is \binom{n−1}{k−1} = \binom{4}{2}. (ii) This is 6. (iii) This is the subset of the list in the solution for part E are no entry is zero:

(3, 1, 1), (2, 2, 1), (2, 1, 2), (1, 3, 1), (1, 2, 2), (1, 1, 3).

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

Solution: Probably the easiest way to convince yourself that this is true is to apply the recurrence from Theorem 4.3.8 several times, expanding only the first term on the right each time and leaving the ones farther to the right unchanged. You will see, after grouping all but the first term with the [,] brackets:

S(n, k) = kS(n − 1, k) + [S(n − 1, k − 1)]
= k^{2}S(n − 2, k) + [kS(n − 2, k − 1) + S(n − 1, k − 1)]
= k^{3}S(n − 3, k) + [k^{2}S(n − 3, k − 1) + kS(n − 2, k − 1) + S(n − 1, k − 1)]
= ⋮

Note that the terms in the square brackets have the form

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

So we can continue this until the step when j = n and at that point the first term outside the square brackets is k^{n}S(n − n, k) = 0. So the identity we are asked to prove follows from the basic recurrence.

This doesn’t quite qualify as a combinatorial proof, though. What’s actually going on here? The proof of the recurrence

S(n, k) = kS(n − 1, k) + S(n − 1, k − 1)

was to argue like this: The left hand side counts the number of distributions of n labeled balls to k unlabeled urns, where no urn is empty. The second term on the right counts the terms where ball 1 is alone in its urn, and the first one counts the cases in which ball 1 occurs together with some other ball in its urn by distributing balls 2, …, n first (S(n−1, k) ways to do that) and then placing ball 1 in one of the urns (k choices for where it goes). This covers all the possibilities, so the recurrence follows from the addition and multiplication principles.

In other words the S(n − 1, k − 1) term counts the cases where you only hit the kth urn with the last ball if you are placing them in reverse order n, n − 1, …, 1. Similarly the kS(n − 1, k) covers all the cases where you have already hit k different urns before you reach the ball 1.

Similarly, for any of these distributions, you can think of placing the balls into the urns in reverse order: n, n − 1, n − 2, . . .. Let i be the number of the ball on which you have “hit” k different urns for the first time. After the previous ball i + 1, the i ball goes to the remaining empty urn at that point (i.e. there’s no choice where it goes). But then the remaining i − 1 balls can go anywhere, and there are k^{i−1} ways to place them. There are S(n − i, k − 1) ways to distribute balls n, n − 1, …, i + 1 to the k − 1 urns that are filled at that point. Hence there are k^{i−1}S(n − i, k − 1) ways to do the distribution that satisfy the condition that you hit all k urns for the first time with ball i. Summing i = 1 to i = n covers all possible cases (but many of the terms will be zero, since S(m, k −1) = 0 if m < k − 1.

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?

Solution: The undecorated boiled eggs are effectively indistinguishable, i.e. unlabeled; they represent the “balls.” The children are labeled (by names, ... ); they represent the urns. Hence in the first case, the number of distributions is \binom{20+10−1}{10−1} = \binom{29}{9}. (Note: This is the “dividers” or “stars and bars” case!) This number includes cases where at least one child gets no eggs. The number of distributions where everyone gets at least one egg is \binom{20−1}{10−1} = \binom{19}{9}. Finally, if we decorate the eggs in a distinguishable way, then there are 10^{20} ways to distribute the eggs with no restrictions, and 10!S(20, 10) ways if every child gets at least one egg.

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(!))

Solution: Y can appear 0, 1, or 2 times and Z must appear the same number of times. In case both are 0, then we want the coefficient of x^{12} in

(1 + x^{3})(1 + x^{2} + x^{4} + x^{6} + x^{8} + x^{10} + x^{12})(x^{4} + x^{5} + ⋯ + x^{12})

In case both are 1, then there are 10 remaining letters and we want the coefficient of x^{10} in

(1 + x^{3})(1 + x^{2} + x^{4} + x^{6} + x^{8} + x^{10} + x^{12})(x^{4} + x^{5} + ⋯ + x^{12})

In case both are 2, then there are 8 remaining letters and we want the coefficient of x^{8} in

(1 + x^{3})(1 + x^{2} + x^{4} + x^{6} + x^{8} + x^{10} + x^{12})(x^{4} + x^{5} + ⋯ + x^{12})

The total number is the sum of these three coefficients.

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 ≤?

Solution: This is the case where we use a two-variable generating function. The answer we want is the coefficient of u^{20}v^{18} in the series expansion of the generating function

\frac{1}{1 − u^{3}v^{2}} · \frac{1}{1 − u^{4}v^{2}} · \frac{1}{1 − u^{5}v^{3}} · \frac{1}{1 − u^{2}v^{3}} .

If the second equality was replaced by ≤ we would want the sum of the coefficients of

u^{20}, u^{20}v, u^{20}v^{2}, …, u^{20}v^{18}

You might compute this by finding a truncated expansion of the generating function containing all the needed terms but omitting any terms with v^{k} for k > 18, setting v = 1, then finding the coefficient of u^{20} in the result.

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?

Solution: Recall we have seen that

D_{n} = n! ∑_{m=0}^{n} \frac{(−1)^{m}}{m!} .

Hence

D_{7} = 7!(1 − 1 + \frac{1}{2!} − \frac{1}{3!} + \frac{1}{4!} − \frac{1}{5!} + \frac{1}{6!} − \frac{1}{7!})

This equals 1854. The fraction of derangements is \frac{1854}{7!} = \frac{1854}{5040} ≐ .368. (Recall that lim_{n→∞} \frac{D_{n}}{n!} = \frac{1}{e} ≐ .368 – the fraction for n = 7 agrees with \frac{1}{e} to four decimal places.)

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.

Solution: The values of the initial conditions are obviously correct(!) Substituting directly the left side of the recurrence equation is 6^{n}. The right side is 7 · 6^{n−1} − 6 · 6^{n−2} = (7 − 1)6^{n−1} = 6^{n}. Hence this R_{n} is a solution.

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.

Solution: We have

\begin{aligned}R(x) & = R_{0} + R_{1}x + R_{2}x^{2} + R_{3}x^{3} + ⋯ \\ 7xR(x) & = 7R_{0}x + 7R_{1}x^{2} + 7R_{2}x^{3} + ⋯ \\ −12x^{2}R(x) & − 12R_{0}x^{2} − 12R_{1}x^{3} + ⋯ \end{aligned}

Hence using the recurrence relation and partial fractions

R(x) = \frac{1 − 7x}{1 − 7x + 12x^{2}} = \frac{1 − 7x}{(1 − 3x)(1 − 4x)} = \frac{4}{1 − 3x} + \frac{−3}{1 − 4x}

Expanding in geometric series, we see

R(x) = ∑_{n=0}^{∞}(4 · 3^{n} − 3 · 4^{n})x^{n}

So R_{n} = 4 · 3^{n} − 3 · 4^{n} for all n ≥ 0. (Note: We don’t need to solve for undetermined coefficients this way using the initial conditions because they are built into the low degree terms of R(x).)

C) What would the general solution of a homogeneous recurrence with characteristic

polynomial

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

look like? Solution:

R_{n} = (A + Bn + Cn^{2} + Dn^{3}) · 4^{n} + (E + F n + Gn^{2}) · 5^{n} + H · 6^{n}.

Note: It doesn’t matter what you call the arbitrary constants in these(!) 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.) Solution: The general solution of the homogenenous recurrence is R_{n} = A · 3^{n} + B · 4^{n} The good guess for the particular solution is Cn^{2} + Dn + E. Answer:

R_{n} = \frac{1}{2} · 3^{n} − \frac{28}{27} · 4^{n} + \frac{1}{6}n^{2} + \frac{17}{18}n + \frac{83}{54}.

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.) Solution: Since the inhomogeneous term 4^{n} solves the homogeneous recurrence we need to use the guess n4^{n} for the particular solution. Answer:

R_{n} = 20 · 3^{n} − 19 · 4^{n} + 4n4^{n}.