\problemdata      
        {counting-18} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {S96 PS7} % Source (if known)
        {S02 PS8; S00, PS7} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem} 
Prove the following identity by algebraic manipulation and
by giving a combinatorial argument:


\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\]
\solution{ 
Algebraic:
\begin{eqnarray*}
\binom{n}{k}\binom{n-k}{r-k} &= &\frac{n!}{k!(n-k)!}\frac{(n-k)!}{(r-k)!(n-r)!}\\
&= &\frac{n!}{(n-r)!k!(r-k)!}\\
&= &\frac{n!r!}{r!(n-r)!k!(r-k)!}\\
&= &\frac{n!}{r!(n-r)}\frac{r!}{k!(r-k)!}\\
&= &\binom{n}{r}\binom{r}{k}\\\
\end{eqnarray*}

Combinatoric:
With a group of $n$ balls, I wish to pick a group of $k$ balls and another group of 
$r-k$ balls.  I could do it by picking a group of $r$ balls and then partition it
into sets of $k$ and $r-k$.  On the other hand, I can first pick $k$ balls and then pick $r-k$ balls
from the remaining $n-k$ balls. 
}

\end{problem}
