\magnification=\magstep1
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Review/Practice Problems on Review Sheet for Exam 2}
\centerline{March 31, 2017}
\bigskip
\noindent
{\it Some review/practice problems}
\bigskip
\noindent
{\it Disclaimer:}  These problems are {\it 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.  
\bigskip
\noindent
I.  Find the number of distributions of 5 balls into 3 urns in each of the 
following cases.  For all parts of the question, 
\bigskip
\itemitem{(i)} give the number of distributions as a case of the formulas from Table 4.6, then
\itemitem{(ii)} evaluate the number to a single integer using recurrences, etc., then
\itemitem{(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(!)
\bigskip
\item{A)} Both the balls and the urns are labeled
\item{} {\it 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\cdot 2\cdot 5 = 30$) of these.  Then cases
where three of the balls go in one urn and two go in one of the others ($3\cdot 2\cdot 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\cdot 10\cdot 2 = 60$ of those).  Then cases where there are two balls in 
one urn, two in a second, and 1 in the last ($3\cdot 5\cdot 3 = 90$ of those).   
\item{B)} Same as 1, but no urn is empty
\item{} {\it 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\cdot(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 ${3\choose 2} = 3$ different ways to choose the two balls that end up
in that urn.  Hence the total number here is $18\cdot (3 + 3) + 12\cdot 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$.  
\item{C)} The balls are labeled, but the urns are not labeled
\item{} {\it 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\cdot 3 + 2\cdot 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.  
(${5\choose 3} = {5\choose 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\cdot 3 = 15$) of these.
\item{D)} Same as 3, but no urn is empty
\item{} {\it Solution:}  (i) $S(5,3)$.  (ii) $ = 25$.  (iii) Take the cases from 
C where no urn is empty (the numbers are all nonzero).  
\item{E)} The urns are labeled, but the balls are not labeled
\item{} {\it Solution:}  (i) The number is ${n + k - 1\choose k-1} = {7\choose 2}$.
(ii) This is ${7\cdot 6\over 2} = 21$.  (iii) You can count these by listing 
the vectors $(x,y,z)$ where $x,y,z \ge 0$ are integers (the numbers of balls in 
each urn) and $x + y + z = 5$: 
$$\eqalign{&(5,0,0),(4,1,0), (4,0,1), (3,2,0),(3,1,1), (3,0,2), (2,3,0), (2,2,1),\cr 
            &(2,1,2), (2,0,3), (1,4,0),(1,3,1), (1,2,2), (1,1,3), (1,0,4), (0,5,0),\cr
            &(0,4,1), (0,3,2), (0,2,3), (0,1,4),(0,0,5).}$$
(Note: 21 vectors!)  
\item{F)} Same as 4, but no urn is empty.
\item{} {\it Solution:}  The number is ${n-1\choose k - 1} = {4\choose 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).$$  
\bigskip
\noindent
II.  Give a combinatorial proof of the recurrence
$$S(n,k) = \sum_{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.'')
\bigskip
\noindent
{\it Solution:}  Probably the easiest way to convince yourself that this
is true is to apply the recurrence from Theorem 4.3.8 several times,
{\it 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:
$$\eqalign{S(n,k) &= k S(n-1,k) + [S(n-1,k-1)]\cr
&= k^2 S(n-2,k) + [k S(n-2,k-1) + S(n-1,k-1)]\cr
&= k^3 S(n-3,k) + [k^2 S(n-3,k-1) + k S(n-2,k-1) + S(n-1,k-1)]\cr
&= \quad \vdots}$$
Note that the terms in the square brackets have the form 
$$\sum_{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 {\it combinatorial proof}, though.  What's
actually going on here?  The proof of the recurrence 
$$S(n,k) = k S(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,\ldots,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 $k$th urn with the last ball if you are placing them in reverse order $n,n-1,\ldots,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 {\it reverse order}:  $n,n-1,n-2,\ldots $.  Let $i$ be
{\it 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,\ldots, 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$.  

\bigskip
\noindent
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?  
\bigskip
\noindent
{\it Solution:}  The undecorated boiled eggs are effectively {\it indistinguishable}, i.e. unlabeled; they represent the ``balls.''  The children
are {\it labeled} (by names, ... ); they represent the urns. Hence in the first case, the number of distributions is ${20 + 10 - 1\choose 10 - 1} = {29\choose 9}$.  (Note:  This is the 
``dividers'' or ``stars and bars'' case!)  This number {\it includes cases where at least one child gets no eggs}. The number
of distributions where everyone gets at least one egg is ${20 - 1\choose 10 -1} = {19\choose 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.
\bigskip
\noindent
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:
\item{(i)}  If $V$ is used, then it is used exactly 3 times
\item{(ii)}  $W$ is used an even number of times (possibly $0$ times)
\item{(iii)}  $X$ is used at least 4 times
\item{(iv)}  $Y$ appears no more than 2 times
\item{(v)}  $Z$ appears {\it 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(!))
\bigskip\noindent
{\it 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 + \cdots + 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 + \cdots + 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 + \cdots + x^{12})$$
The total number is the sum of these three coefficients.
\bigskip
\noindent
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:
$$\eqalign{
3x_1 + 4x_2 + 5x_3 + 2x_4 &= 20\cr
2x_1 + 2x_2 + 3x_3 + 3x_4 &= 18\cr}$$
What would change if the second $=$ was replaced by $\le$?
\bigskip
\noindent
{\it 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
$${1\over 1 - u^3 v^2}\cdot {1\over 1 - u^4 v^2} \cdot {1 \over 1 - u^5 v^3} \cdot {1 \over1 -  u^2 v^3}.$$
If the second equality was replaced by $\le$ we would want the sum of the coefficients of 
$$u^{20}, u^{20} v, u^{20} v^2, \ldots, 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.
\bigskip
\noindent
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?
\bigskip
\noindent
{\it Solution:}  Recall we have seen that 
$$D_n = n! \sum_{m=0}^n {(-1)^m \over m!}.$$ 
Hence 
$$D_7 = 7!(1 - 1 + {1\over 2!} - {1\over 3!} + {1\over 4!} - {1\over 5!} + {1 \over 6!} - {1\over 7!})$$
This equals 1854.  The fraction of derangements is ${1854 \over 7!} = {1854\over 5040} \doteq .368$.  (Recall that 
$\lim_{n\to\infty} {D_n\over n!} = {1\over e} \doteq .368$ -- the fraction for $n = 7$ agrees with ${1\over e}$ to four decimal places.)  
\bigskip
\noindent
VII.  Recurrences.
\item{A)}  Show directly (i.e. without solving the recurrence) that $R_n = 6^n$
satisfies $R_n = 7 R_{n-1} - 6R_{n-2}$, and $R_0 = 1$, $R_1 = 6$.  
\item{} {\it 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\cdot 6^{n-1} - 6\cdot 6^{n-2} = (7 - 1)6^{n-1} = 6^n$.  Hence this $R_n$ is a solution.
\item{B)}  Solve the following homogeneous recurrence using the generating function method:
$$R_n = 7 R_{n-1} - 12 R_{n-2}$$
with initial conditions $R_0 = 1$ and $R_1 = 0$.  
\item{}{\it Solution:}  We have 
$$\eqalign{R(x) &= R_0 + R_1 x + R_2 x^2 + R_3 x^3 + \cdots \cr
                 7xR(x) &= \qquad 7R_0 x + 7R_1 x^2 + 7R_2 x^3 + \cdots \cr
                -12 x^2 R(x) &\qquad\qquad\qquad -12 R_0x^2 - 12R_1 x^3 + \cdots\cr}$$
Hence using the recurrence relation and partial fractions
$$R(x) = {1 - 7x\over 1 - 7 x + 12 x^2} = {1 - 7x\over (1 - 3x)(1 - 4x)} = {4\over 1 - 3x} + {-3\over 1 - 4x}$$
Expanding in geometric series, we see
$$R(x) = \sum_{n=0}^\infty (4\cdot 3^n - 3\cdot 4^n) x^n$$
So $R_n = 4\cdot 3^n - 3\cdot 4^n$ for all $n \ge 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)$.)
\item{C)}  What would the general solution of a homogeneous recurrence with
characteristic polynomial 
$$(1 - 4x)^4 (1 - 5x)^3 (1 - 6x)$$
look like?
\item{} {\it Solution:}
$$R_n = (A + Bn + Cn^2 + Dn^3)\cdot 4^n + (E + F n + Gn^2)\cdot 5^n + H\cdot 6^n.$$
Note:  It doesn't matter what you call the arbitrary constants in these(!)
\item{D)}   Solve the following inhomogeneous recurrence using our ``shortcut''
method and undetermined coefficients:
$$R_n = 7 R_{n-1} - 12 R_{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.)
\item{} {\it Solution:}  The general solution of the homogenenous recurrence
is
$R_n = A \cdot 3^n + B\cdot 4^n$
 The good guess for the particular solution is $C n^2 + D n + E$.  Answer:  
$$R_n = {1\over 2}\cdot 3^n - {28\over 27}\cdot 4^n +{1\over 6} n^2 + {17\over 18} n + {83\over 54}.$$ 
\item{E)}   Solve the following inhomogeneous recurrence using our ``shortcut''
method and undetermined coefficients:
$$R_n = 7 R_{n-1} - 12 R_{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.)
\item{} {\it Solution:}  Since the inhomogeneous term $4^n$ solves the homogeneous recurrence we need to 
use the guess $n 4^n$ for the particular solution.   Answer:  
$$R_n = 20\cdot 3^n - 19\cdot 4^n + 4n4^n.$$
\bye
