
\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Solutions for Midterm Examination 2 -- April 7, 2017}
\bigskip
\noindent
I.  
\item{A)} (5)  What is the definition of the Stirling number of the second
kind, $S(n,k)$, in terms of distribution problems? 
\item{} {\it Solution:}  $S(n,k)$ is the number of ways of distributing
$n$ labeled balls to $k$ unlabeled urns where no urn is empty.  
\item{B)} (15)  State and prove the recurrence relation for the $S(n,k)$. 
\item{}  {\it 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,\ldots,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,\ldots,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\cdot S(n-1,k)$ distributions of this type by the multiplication
principle.  By the addition principle, then $S(n,k) = k S(n-1,k) + S(n-1,k-1)$.
\item{C)} (5)  Determine the Stirling number $S(6,2)$.
\item{} {\it Solution:}  Applying the recurrence, 
$$\eqalign{S(6,2) &= 2\cdot S(5,2) + S(5,1)\cr
                  &= 2 \cdot (2\cdot S(4,2) + S(4,1)) + 1\cr
                  &= 2 \cdot (2\cdot (2\cdot S(3,2) + S(3,1)) + 1) + 1\cr
                  &= 2 \cdot (2\cdot (2\cdot 3 + 1) + 1) + 1\cr
                  &= 31.\cr}$$
\bigskip
\noindent
II.  For all parts of this question, express the number of distributions
in terms of partition numbers, Stirling numbers, binomial coefficients, etc.
{\it You do not need to evaluate any of these to a single number.}
\item{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?
\item{} {\it 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).  
\item{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?
\item{} {\it Solution:}  Now the urns are labeled and no urn is empty, but the balls are
still unlabeled, so the number is ${10 - 1\choose 4 - 1} = {9\choose 3}$.  
\item{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)?
\item{} {\it 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).  
\item{D)}  (5) What changes in part C) if every pile gets at least one pad?
\item{} {\it Solution:}  Only the $S(10,4)$ term is included.  
\bigskip
\noindent
III.  (15) 100 pencils are divided into four
lots of sizes $x_1,x_2,x_3,x_4$, each a {\it multiple of 5}.
and placed in 4 classrooms.  
Room 1 receives {\it at least $20$\/} pencils, room 2 receives {\it no more than $40$} pencils,
room 3 receives {\it between $15$ and $25$} pencils, and room 4 receives a number of pencils
that is a {\it 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 {\it generating
function} and explain how you would use it to answer this question.
\bigskip
\noindent
{\it 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} + \cdots)(1 + x^5 + x^{10} + \cdots + x^{40})(x^{15} + x^{20} + x^{25})(1 + x^{10} + x^{20} + \cdots)$$
or 
$${x^{20}(1 + x^5 + \cdots + x^{40})(x^{15} + x^{20} + x^{25})\over (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.  
\bigskip
\noindent
IV. (15) For each $n \ge 1$, let $T_n$ be the number of ways of
arranging $n$ ``triominoes'' (like dominoes, but $3\times 1$) in a $3\times 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$.
({\it Don't try to solve the recurrence.})
\bigskip
\noindent
{\it 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 \times (n-1)$ tray
can come after that.  Or else, you can have three triominoes stacked horizontally
in a $3\times 3$ block, and then any configuration in a $3 \times (n - 3)$ tray
after that.  So every $3\times n$ configuration is in one of these cases and the number
is $T_n = T_{n-1} + T_{n-3}$.  
\bigskip
\noindent
V.  
\item{A)} (20) A sequence $R_n$ is defined by the recurrence
$R_n = 6R_{n-1} - 8R_{n-2}$. Express the 
{\it 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.)
\item{} {\it 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) = {3 - 17x\over 1 - 6x + 8x^2}$$
Now, using partial fractions, we have
$$ = {3 - 17x\over (1 - 4x)(1 - 2x)} = {11/2\over 1 - 2x} + {-5/2\over 1 - 4x}.$$
So expanding in geometric series, we see that 
$$R_n = {11\over 2} \cdot 2^n - {5\over 2} 4^n.$$
\item{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$.  
\item{} {\it 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 $C n 2^n$.  The full solution
will be $A\cdot 2^n + B\cdot 4^n + C n 2^n$ for some constants $A,B,C$.  
From the initial conditions and the value of $R_2$ computed below, we have
$$\eqalign{R_0 = 1 &= A + B\cr
           R_1 = 1 &= 2A + 4B + 2C\cr
           R_2 = 6\cdot 1 - 8\cdot 1 + 4 = 2 &= 4A + 16B + 8C\cr}$$
The solution of this system is $A = {1\over 2}, B = {1\over 2}, C = -1$.  So the solution of 
the recurrence is
$${1\over 2}\cdot 2^n + {1\over 2}\cdot 4^n - n\cdot 2^n.$$
\bye

