\problemdata
{permutation with repetition}
{f01 ps9}
{s99}

\begin{problem} Let $A=\{a_1,a_2,...,a_n\}$ be some set of $n$ items.  Remember
that the number of permutations \emph{with repetition} of the elements of
$A$, where each element $a_i$ is repeated exactly $r_i$ times, is
\[
\binom{r_1+r_2+...+r_n}{r_1, \ r_2, \ ..., \ r_n} ::=
 \frac{(r_1+r_2+...+r_n)!}{r_1!  r_2!  ...  r_n!}
\]

\begin{problemparts}

\problempart Give a simple algebraic proof that
\[
\binom{a+b+c+d}{a} \binom{b+c+d}{b,c,d} 
 = \binom{a+b+c+d}{d} \binom{a+b+c}{c} \binom{a+b}{b}.
\]

\solution{
\begin{eqnarray*}
\binom{a+b+c+d}{a} \binom{b+c+d}{b,c,d} & = &
   \frac{(a+b+c+d)!}{a!\, (b+c+d)!} \frac{(b+c+d)!}{b!\, c!\, d!}\\
& = & \frac{(a+b+c+d)!}{a!} \frac{1}{b!\, c!\, d!}\\
& = & \frac{(a+b+c+d)!}{a!\, b!\, c!\, d!}\\
& = & \binom{a+b+c+d}{a, b, c, d}.
\end{eqnarray*}

Also
\begin{eqnarray*}
\binom{a+b+c+d}{d} \binom{a+b+c}{c} \binom{a+b}{b} & = &
  \frac{(a+b+c+d)!}{d!\, (a+b+c)!} \frac{(a+b+c)!}{c!\, (a+b)!}
  \frac{(a+b)!}{b!\, a!}\\
& = &   \frac{(a+b+c+d)!}{d!} \frac{1}{c!} \frac{1}{b!\, a!}\\
& = & \frac{(a+b+c+d)!}{a!\, b!\, c!\, d!}\\
& = & \binom{a+b+c+d}{a, b, c, d}.
\end{eqnarray*}
}

\problempart Now give a \emph{combinatorial argument} proving this equation.
That is, describe two different procedures for counting the same things,
where the lefthand side of the equation clearly describes the number of
outcomes of the first procedure, and the righthand side the number of
outcomes of the second procedure.

\solution{Both expressions equal
\[
\binom{a+b+c+d}{a,b,c,d}
\]
and correspond to choosing a permutation of four kinds of items in
quantities $a,b,c$ and $d$, respectively.  Now the LHS corresponds to
first choosing positions in the permutation for $a$ items of the first
kind, then for $b,c$, and $d$ of the remaining three kinds.  The RHS
corresponds to first choosing $d$ of the fourth kind, then $c$ of the
third kind, and then $b$ of the second kind.}

\end{problemparts}
\end{problem}
