\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 5}
\centerline{March 17, 2017}
\vskip 10pt
\noindent
4.3.13.  (Recall the directions for the problem I gave said to interchange the 16 and the 9 
so there are 16 balls and 9 urns!)  Also refer to Table 4.6 on page 109.
\vskip 10pt
(i)  This is the number of {\it partitions} of 16 things into 9 or fewer parts,  $\sum_{k=1}^{9} p(16,k)$.  
This form by itself was acceptable.  If you compute the value, you want to use the recurrence for these
partition numbers given in Theorem 4.3.4 in Beeler.  
(These are numbers of {\it partitions, not permutations!})  The correct numbers are:
\begin{eqnarray*} p(16,1) &=& 1,\ p(16,2)\ =\ 8,\ p(16,3)\ =\ 21,\ p(16,4)\ =\ 34,\ p(16,5)\ =\ 37,\\ 
                  p(16,6) &=& 35,\ p(16,7)\ =\ 28,\ p(16,8)\ =\ 22,\ p(16,9)\ =\ 15.
\end{eqnarray*}
The total should be $\sum_{i=1}^9 p(16,i) = 201$.  
I computed these with a {\it recursive procedure} in Maple based on the recurrence:
\begin{verbatim}
                    pnk := proc(n, k) 
                    if n < k then 
                      return(0)
                    elif n = k then 
                      return(1) 
                    elif k = 1 then 
                      return(1) 
                    else 
                      return(pnk(n-1,k-1)+pnk(n-k,k)) 
                    end if 
                    end proc:
\end{verbatim}
\vskip 10pt
(ii)  This is $p(16,9) = 15$.  (Note that $p(9,16) = 0$ so this question is slightly silly
as stated!)
\vskip 10pt
(iii)  This is $9^{16}$ by the Multiplication Principle ($9$ choices for the urn the first
ball goes to, then $9$ choices again for the second ball, etc.)
\vskip 10pt
(iv)  This is the Stirling number of the second kind $S(16,9) = 820784250$.  The $S(n,k)$
can be computed in Maple using a procedure with the same outline as the one above, but
using the recurrence from Theorem 4.3.8:
$$S(n,k) = kS(n-1,k) + S(n-1,k-1)$$
\vskip 10pt
(v)  This is $9!\cdot S(16,9)$.
\vskip 10pt
\noindent
4.3.17 (i)  $p_2(n,k)$ is the number of partitions of $n$ into $k$ integers each at least
$2$.  If the smallest part in the partition is a $2$, then removing one of the $2$'s gives a 
partition of $n - 2$ with $k - 1$ parts, each of which is at least $2$.  Conversely, starting
from such a partition of $n-2$ and adding $2$ gives a partion of $n$ of the type
we are considering.   If the smallest
part in the partition is a $3$, then similarly, removing one of the $3$'s gives a partition
of $n - 3$ with $k = 1$ parts, each of which is at least 3 and conversely.  Otherwise, 
each part is at least 4.  We subtract two from each of the parts, yielding a partition
of $n - 2k$ into $k$ parts, all of which are at least two.  Every partition counted by 
$p_2(n,k)$ falls into one of these categories, and the categories are pairwise disjoint.  
Hence by the Addition Principle, 
$$p_2(n,k) = p_2(n-2,k-1) + p_3(n-3,k-1) + p_2(n-2k,k).$$
\vskip 10pt
\noindent
4.3.18.  (The idea here is similar to the proof of Theorem 4.3.8 -- the recurrence
relation for the Stirling numbers of the second kind.)
We have that $S(n+1,k)$ gives the number of ways to distribute $n+1$ balls into
$k$ urns where the balls are labeled, the urns are unlabeled and no urn is empty.  
The idea is to break up the possible distributions based on which other balls
end up together with ball 1 (recall, they're labeled!).
\begin{itemize}
\item If ball 1 is alone, the other $n$ balls get distributed among the remaining
$k - 1$ urns with none empty, so $\binom{n}{n} S(n,k-1)$ such distributions;
\item If ball 1 is with one other ball, there are $\binom{n}{n-1}$ possible choices
for the ones not with ball 1, and those other $n - 1$ balls get distributed among the remaining $k - 1$ 
urns with none empty, so $\binom{n}{n-1} S(n-1,k-1)$ of these;
\item If ball 1 is with $j$ other balls, there are $\binom{n}{n-j}$ possible choices
for the remaining balls, and those other $n - j$ balls get distributed among the remaining $k - 1$ 
urns with none empty, so $\binom{n}{n - j} S(n - j,k-1)$ of these.
\end{itemize}
Hence summing over the numbers $j$ by the Addition Principle, we have
$$S(n+1,k) = \sum_{j=0}^n \binom{n}{n-j} S(n - j,k-1) = \sum_{i=0}^n \binom{n}{i} S(i,k-1)$$
where the last equality just comes from re-indexing the sum with $i = n - j$.  
(Comments:  
\begin{enumerate}
\item Not all of the terms in this sum will be nonzero, of course.
\item You can think of the $i$ in the binomial coefficient as {\it either} the 
number of balls $2,\ldots, n+1$ besides the balls with ball 1, or as
the number of balls $2,\ldots, n+1$ with ball 1. One set is the complement of the other 
inside the set of balls other than ball 1.  Recall the binomial coefficient
identity:
$$\binom{n}{n - j} = \binom{n}{j}.$$
I explained this both ways with different people in office hours, so don't
get confused if it looks as though it's reversed from the way you were thinking
about it!)
\end{enumerate}
\vskip 10pt
\noindent
4.3.20. We have that $S(n,k)$ gives the number of ways to distribute $n$ balls into
$k$ urns where the balls are labeled, the urns are unlabeled and no urn is empty. 
Suppose we {\it temporarily label} the urns using the integers in $[k]$.  Then the 
numbers of balls in the urns, $\lambda_1,\ldots,\lambda_k$ must sum to $n$ and
they must all be greater than or equal to $1$.  By the labeled urns case, we know
that the number of different distributions where the $k$th urn gets $\lambda_k$ balls
is given by the multinomial coefficient
$$\binom{n}{\lambda_1,\ldots,\lambda_k}$$ 
and the total number of possible distributions is 
$$\sum \binom{n}{\lambda_1,\ldots,\lambda_k}$$
where the sum is over all the $k$-tuples $(\lambda_1,\ldots,\lambda_k)$ with 
$\lambda_1 + \cdots + \lambda_k = n$ and $\lambda_i \ge 1$ for all $i$.  
Now {\it take the labels off the urns}.  The only thing we can distinguish now
is when urns have different numbers of balls.  So if $a_i$ is the number of times
the integer $i$ appears in the list $\lambda_1,\ldots,\lambda_k$ from before, then
there are $a_1! a_2! \cdots a_n!$ possible different labelings in the first step yielding the 
same eventual unlabeled distribution.  Hence 
$$S(n,k) = \sum \binom{n}{\lambda_1,\ldots,\lambda_k}\cdot \frac{1}{a_1!a_2! \cdots a_n!}$$
where the summation is over the $k$-tuples $\lambda_1,\ldots,\lambda_k$ as before.
\vskip 10pt
\noindent
5.1.10. (i) We have
$$4x^2 - 20x + 24 = 24\left(1 - \frac{5}{6} x + \frac{1}{6} x^2\right) 
= 24\left(1 - \frac{1}{3}x\right)\left(1 - \frac{1}{2}x\right).$$ 
(ii) We have
$$6 - 5x - 2x^2 + x^3 = 6\left(1 - \frac{5}{6}x - \frac{1}{3} x^2 + \frac{1}{6} x^3\right)$$
We see (e.g. by the Rational Roots Test) that $x = 1$ is a root and that starts the factorization:
$$=6(1 - x)\left(1 + \frac{1}{6} x - \frac{1}{6} x^2\right) 
= 6(1 - x)\left(1 - \frac{1}{3}x\right)\left(1 + \frac{1}{2}x\right).$$ 
\vskip 10pt 
\noindent
5.1.11.  We write
$$\frac{5x - 12}{x^2 - 5x + 6} = \frac{5x - 12}{(x - 2)(x - 3)} = \frac{A}{x - 2} + \frac{B}{x - 3}.$$
Then clearing denominators gives
$$5x - 12 = A(x - 3) + B(x - 2) = (A + B)x + (-3A - 2B).$$
Hence $A + B = 5$ and $-3A - 2B = -12$, so $A = 2$ and $B = 3$.  This gives
$$\frac{5x - 12}{x^2 - 5x + 6} = \frac{2}{x - 2} + \frac{3}{x - 3} = \frac{-1}{1 - x/2} + \frac{-1}{1 - x/3}$$
The reason for writing it in the final form is explained in \S 5.2(!)
\vskip 10pt
\noindent
5.2.8.  Start from the geometric series formula
$$\frac{1}{1 - x} = \sum_{n=0}^\infty x^n$$
This series converges for all $x$ with $|x| < 1$ to the function on the left, so we can
differentiate twice with respect to $x$ to yield
$$\frac{2}{(1 - x)^3} = \sum_{n=0}^\infty n(n-1) x^{n-2}$$
Since the terms on the right with $n = 0,1$ now are zero we can reindex the sum with
$n-2 = m$ or $n = m + 2$.  This yields, after dividing both sides by $2$:
$$\frac{1}{(1 - x)^3} = \sum_{m=0}^\infty \frac{(m+2)(m+1)}{2} x^m.$$
This series converges on the same interval, namely for all $|x| < 1$.  
\vskip 10pt 
5.2.10.  We first factor the bottom as in 5.1.10 above, then compute the partial fraction
decomposition, then apply the geometric series formula:
\begin{eqnarray*}
\frac{3}{1 - 5x + 6x^2} &=& \frac{3}{(1 - 2x)(1 - 3x)}\\
&=& \frac{-6}{1 - 2x} + \frac{9}{1 - 3x}\\
&=& (-6)\cdot \sum_{k=0}^\infty(2x)^k + 9\cdot \sum_{k=0}^\infty (3x)^k\\
&=& \sum_{k=0}^\infty \left(-6\cdot 2^k + 9\cdot 3^k\right) x^k.
\end{eqnarray*}
\end{document}
