Mathematics 357 – Combinatorics Solutions for Midterm Examination 2 – April 7, 2017

I. A) (5) What is the definition of the Stirling number of the second kind, S(n, k), in terms

of distribution problems? Solution: S(n, k) is the number of ways of distributing n labeled balls to k unlabeled urns where no urn is empty.

B) (15) State and prove the recurrence relation for the S(n, k).

Solution: The recurrence is S(n, k) = kS(n − 1, k) + S(n − 1, k − 1). Proof: Every distribution of the n labeled balls will either have (a) ball 1 alone in its urn, or else (b) ball 1 together with some other ball. (a) Suppose ball 1 is alone in its urn. Then the n − 1 balls 2, …, n can be distributed in every possible way to the other k − 1 urns. So there are S(n − 1, k − 1) distributions of this type. (b) On the other hand, if ball 1 appears with some other ball in its urn, then the n − 1 balls 2, …, n can be distributed in any way so that none of the urns is empty (S(n − 1, k) ways to do that), and then ball 1 can be placed arbitrarily in any urn (k choices). Hence there are k · S(n − 1, k) distributions of this type by the multiplication principle. By the addition principle, then S(n, k) = kS(n − 1, k) + S(n − 1, k − 1).

C) (5) Determine the Stirling number S(6, 2).

Solution: Applying the recurrence,

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

II. For all parts of this question, express the number of distributions in terms of partition numbers, Stirling numbers, binomial coefficients, etc. You do not need to evaluate any of these to a single number. A) (5) How many ways are there to distribute 10 identical unmarked pads of paper into

4 piles, with no restrictions on the sizes of the piles? Solution: This is the unlabeled balls (the pads), unlabeled urns (piles) case. So the number is p(10, 4) + p(10, 3) + p(10, 2) + p(10, 1) (sum of partition numbers).

B) (5) How many ways are there if the piles of pads are supposed to go to 4 numbered tables and at least one pad goes to each table? Solution: Now the urns are labeled and no urn is empty, but the balls are still unlabeled, so the number is \binom{10−1}{4−1} = \binom{9}{3}.

C) (5) How many ways are there if the pads have 10 different colors of paper but we’re back in the situation of part A (i.e. just 4 piles, not the 4 numbered tables)? Solution: Now the balls are labeled but the urns are not. The number is S(10, 4) + S(10, 3)+S(10, 2)+S(10, 1) (since no restrictions on how many are in each group and some can have no paddles).

D) (5) What changes in part C) if every pile gets at least one pad?

Solution: Only the S(10, 4) term is included.

III. (15) 100 pencils are divided into four lots of sizes x_{1}, x_{2}, x_{3}, x_{4}, each a multiple of 5. and placed in 4 classrooms. Room 1 receives at least 20 pencils, room 2 receives no more than 40 pencils, room 3 receives between 15 and 25 pencils, and room 4 receives a number of pencils that is a multiple of 10. How many different vectors (x_{1}, x_{2}, x_{3}, x_{4}) of numbers of pencils satisfy these conditions? Set up an appropriate generating function and explain how you would use it to answer this question.

Solution: The generating function is (left to right, the factors correspond to rooms 1,2,3,4 in that order):

(x^{20} + x^{25} + x^{30} + ⋯)(1 + x^{5} + x^{10} + ⋯ + x^{40})(x^{15} + x^{20} + x^{25})(1 + x^{10} + x^{20} + ⋯)

or

\frac{x^{20}(1 + x^{5} + ⋯ + x^{40})(x^{15} + x^{20} + x^{25})}{(1 − x^{5})(1 − x^{10})}.

To answer the question, you would look for the coefficient of x^{100} in the Taylor series expansion of the rational function given second, or in the expansion of the product given in the first form.

IV. (15) For each n ≥ 1, let T_{n} be the number of ways of arranging n “triominoes” (like dominoes, but 3 × 1) in a 3 × n tray with no overlapping. Find a recurrence relation of order 3 for the T_{n} sequence and the initial values T_{1}, T_{2}. (Don’t try to solve the recurrence.)

Solution: The recurrence is

T_{n} = T_{n−1} + T_{n−3},

with initial conditions T_{1} = T_{2} = 1, T_{3} = 2. The idea is that if you look at the left most group of triominoes, there are only two possibilities. You either have one vertical triomino, and then any configuration in a 3 × (n − 1) tray can come after that. Or else, you can have three triominoes stacked horizontally in a 3 × 3 block, and then any configuration in a 3 × (n − 3) tray after that. So every 3 × n configuration is in one of these cases and the number is T_{n} = T_{n−1} + T_{n−3}.

V. A) (20) A sequence R_{n} is defined by the recurrence R_{n} = 6R_{n−1} − 8R_{n−2}. Express the

generating function of the sequence R_{n} as a rational function of x if the initial terms are R_{0} = 3, R_{1} = 1 and use it to derive a formula for R_{n} as a function of n. (Partial credit 10 for solution by the “shortcut” method.) Solution: The generating function R(x) satisfies

(1 − 6x + 8x^{2})R(x) = R_{0} + (R_{1} − 6R_{0})x = 3 − 17x

so

R(x) = \frac{3 − 17x}{1 − 6x + 8x^{2}}

Now, using partial fractions, we have

= \frac{3 − 17x}{(1 − 4x)(1 − 2x)} = \frac{11/2}{1 − 2x} + \frac{−5/2}{1 − 4x}.

So expanding in geometric series, we see that

R_{n} = \frac{11}{2} · 2^{n} − \frac{5}{2}4^{n}.

B) (15) Now suppose we wanted to solve R_{n} = 6R_{n−1} − 8R_{n−2} + 2^{n}. What would be the appropriate “good guess” for the particular solution? See table from Beeler on back. Determine the solution of this recurrence with the initial conditions R_{0} = 1, R_{1} = 1. Solution: Since the 2^{n} is also a solution of the homogeneous recurrence as in part A, we need a particular solution of the form Cn2^{n}. The full solution will be A · 2^{n} + B · 4^{n} + Cn2^{n} for some constants A, B, C. From the initial conditions and the value of R_{2} computed below, we have

\begin{aligned}R_{0} = 1 & = A + B \\ R_{1} = 1 & = 2A + 4B + 2C \\ R_{2} = 6 · 1 − 8 · 1 + 4 = 2 & = 4A + 16B + 8C \end{aligned}

The solution of this system is A = \frac{1}{2}, B = \frac{1}{2}, C = −1. So the solution of the recurrence is

\frac{1}{2} · 2^{n} + \frac{1}{2} · 4^{n} − n · 2^{n}.