\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 4}
\centerline{March 3, 2017}
\vskip 10pt
\noindent
3.6.12.  (i) We have
$$\binom{11}{3,2,6} = \frac{11!}{3!2!6!} = 4620.$$
(ii) Similarly, 
$$\binom{27}{8,7,3,9} = \frac{27!}{8!7!3!9!} = 24610330602000.$$
\vskip 10pt
\noindent
3.6.14.  (i) The coefficient of $x^3y^4z^5$ in $(x + y + z)^{12}$ is the multinomial
coefficient
$$\binom{12}{3,4,5} = 27720.$$
(iii) Think of evaluating $(w + 2x + 3y + 4z)^{15}$ and then setting $w = 1$.  
The coefficient of $x^3y^4z^5$ in $(1 + 2x + 3y + 4z)^{15}$ is
$$\binom{15}{3,3,4,5}\cdot 2^3\cdot 3^4\cdot 4^5 = 8369115955200.$$
\vskip 10pt
\noindent
3.6.19.  The idea is that we want to count the distinguishable permuations of 
the letters in the word ``COMBINATORICS."  The point is that the two ``C"s are not distinguishable, 
and similarly for the two ``O"s and two ``I"s.  The number of distinguishable permutations is
$$\binom{13}{2,2,2,1,1,1,1,1,1,1} = \frac{13!}{2!2!2!(1!)^7} = 778377600.$$
(See Example 3.6.9.)
\vskip 10pt
\noindent
3.6.23. The groups are unlabeled, so groups of the same size are indistinguishable.
The three groups of five are all the same and similarly for the five groups of three.
The number is
$$\binom{30}{3,3,3,3,3,5,5,5}\cdot\frac{1}{3!}\frac{1}{5!} = 27417483351786528000$$
(a very large number of them!) This is similar to Example 3.6.11.
\vskip 10pt
\noindent
3.6.24.  {\it Algebraic proofs:  This is the most direct approach, I think.}  (i)  By the Multinomial Theorem (3.6.4), 
$$(x + y + z)^n = \sum_{\substack{\lambda_1 + \lambda_2 + \lambda_3 = n\\ \lambda_1,\lambda_2,\lambda_3\ge 0}}
\binom{n}{\lambda_1,\lambda_2,\lambda_3} x^{\lambda_1} y^{\lambda_2} z^{\lambda_3}$$
Substituting $x = y = z = 1$ we get the identity we want.  (This is also the special case of Corollary
3.6.7 where $k = 3$.)

(ii) In the identity from part (i), before substituting $x = y = z = 1$, take the partial
derivative with respect to $x$:
$$n(x + y + z)^{n-1} = \sum_{\substack{\lambda_1 + \lambda_2 + \lambda_3 = n\\ \lambda_1,\lambda_2,\lambda_3\ge 0}}
\binom{n}{\lambda_1,\lambda_2,\lambda_3}\lambda_1 x^{\lambda_1-1} y^{\lambda_2} z^{\lambda_3}$$
Then substitute $x = y = 1$ again to yield the identity we want.

(iii) This is obtained similarly from the identity in (i) by computing the mixed second-order partial
derivative $\frac{\partial^2}{\partial x\partial y}$
then substituting $x = y = z = 1$.  (Or, differentiate with respect to $y$ in the identity from part (ii)
before substituting $x = y = z = 1$.)

But of course, there are also {\it combinatorial proofs}.  (i) Think of taking $n$ labeled balls and
placing them into $3$ labeled urns.  The total number of ways to do this is $3^n$ by the Multiplication
Principle ($3$ choices for each ball).  The other side breaks the number of ways to do the distribution
into the number of ways with given numbers of balls in each urn: $\lambda_j$ is the number of balls
in urn $j$.  Since all the balls are distributed, $\lambda_1 + \lambda_2 + \lambda_3 = n$ and $\lambda_i \ge 0$, 
and $\binom{n}{\lambda_1,\lambda_2,\lambda_3}$ gives the number of ways the distribution could 
be done to get those numbers of balls in the three urns.  The left side is equal to the right
side by the Addition Principle.  You can also think of this in terms of $n$ people being assigned
to $k = 3$ different labeled committees.

(ii)  Suppose $n$ people being assigned
to $k = 3$ different labeled committees and the first committee is non-empty and has at least a chair
person.  There are $\binom{n}{1} = n$ people who can be chair of that committee and $n - 1$ other
people, each of whom can get assigned to any one of the three committees.  By the Multiplication Principle, 
the total number of distributions of people is $n 3^{n-1}$.  On the other hand the term
$$\binom{n}{\lambda_1,\lambda_2,\lambda_3} \lambda_1 = \binom{n}{\lambda_1,\lambda_2,\lambda_3} 
\binom{\lambda_1}{1}$$
counts the number of distributions of the $n$ people into the three committees of those sizes, and the 
selection of a chair from membership of the first committee. Then we sum over all 3-tuples
$\lambda_i$ such that $\lambda_1 + \lambda_2 + \lambda_3 = n$.   The two sides are equal by the 
Addition Principle.  The terms on the right account for all the possible sizes of committees,
and those possibilities are pairwise disjoint.  (Comment:  You might notice that, by saying
committee 1 must have a chairperson, I am restricting
to the case where committee 1 has $\lambda_1 \ge 1$.  That is OK because 
$\binom{n}{\lambda_1,\lambda_2,\lambda_3} \lambda_1 = 0$ if $\lambda_1 = 0$.  Those terms get
added into the sum, but they don't contribute anything to it.)

(iii)  Similarly, suppose both committees 1 and 2 have chairpersons.  There are
$n(n-1)3^{n-2}$ ways to distribute the people as a chair for committee 1, a chair for committee 2, and
$n - 2$ other people who can end up in any one of the committees.  
 On the other hand the term
$$\binom{n}{\lambda_1,\lambda_2,\lambda_3} \lambda_1 \lambda_2 = \binom{n}{\lambda_1,\lambda_2,\lambda_3} 
\binom{\lambda_1}{1} \binom{\lambda_2}{1}$$
counts the number of distributions of the $n$ people into the three committees of those sizes, and the 
selection of a chairs from membership of the first and second committees.  Summing over all 
triples of $\lambda_i$ with sum = $n$, we get the left-hand side, counted a different way.  
As before, note 
$$\binom{n}{\lambda_1,\lambda_2,\lambda_3} \lambda_1 \lambda_2 = 0$$
if $\lambda_1 = 0$ or $\lambda_2 = 0$.  

\vskip 10pt
\noindent
4.2.13.  
(i) As in Proposition 4.2.14, we could interpret this as the number of ways to 
distribute $11$ {\it labeled, i.e. distinguishable} balls into 3 {\it labeled, i.e. distinguishable}
urns such that the first urn gets 4 balls, the second urn gets 5 balls and the last urn gets 2 balls.

(ii)  Say the balls are labeled with the numbers in $[11]$.  Since each urn gets at least one ball, 
the ball 11 can end up in any of the three urns.  So the number of assignments of balls into 
urns can be computed by the Addition Principle, breaking into three cases depending on which 
urn ball 11 goes to.  In the first term we count the ways the other 10 balls could get
distributed to the urns if ball 11 goes to urn 1, and similarly for the others:
$$\binom{11}{4,5,2} = \binom{10}{3,5,2} + \binom{10}{4,4,2} + \binom{10}{4,5,1}.$$

(iii)  This can be generalized in several ways:  The total number of balls can be any integer $n$, 
there can be any number $k$ of urns, and the number of balls that go to each of the urns
can be any $k$ strictly positive integers $\lambda_i, i = 1,\ldots, k$ adding up to $n$.  The 
corresponding identity is
$$\binom{n}{\lambda_1,\ldots,\lambda_i,\ldots,\lambda_k} = 
\sum_{i=1}^k \binom{n-1}{\lambda_1,\ldots,\lambda_i - 1,\ldots,\lambda_k}$$
The proof is the same as in part (ii).  
\vskip 10pt
\noindent
4.2.14.  I'm going to interpret the given information like this:  The $n = 15$ dollar bills ($=$ the ``balls")
are indistinguishable (for instance, they have no special markings and we can ignore
the other information such as the serial number, the year of issue, the signature of the US Treasurer, etc. -- 
who ever looks at those?).
But it makes more sense to think of the $k = 10$ children ($=$ the ``urns") 
as distinguishable, or labeled (they have names, presumably!)  So this is 
the situation for ``dividers" as in Proposition 4.2.7.  The number is
$$\binom{(n-k) + k-1}{k - 1} = \binom{n-1}{k-1} = \binom{14}{9} = 2002.$$
\vskip 10pt
\noindent
4.2.17.  (i) This is the situation of Theorem 4.2.6:  The number is 
$$\binom{25 + 4}{4} = \binom{29}{4} = 23751.$$

(ii)  This is the situation of Proposition 4.2.7.  The number is 
$$\binom{(25 - 5) + 4}{4} = \binom{24}{4} = 10626.$$

(iii)  Distribute the first 17 gumdrops as described in the statement of the problem.  Then
the remaining $25 - 17 = 8$ can go to any one of the five children, so this is the situation
of Theorem 4.2.6 again, but with $n = 8$:
$$\binom{8 + 4}{4} = \binom{12}{4} = 495.$$
\end{document}
