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


\begin{problem}
You want to choose a team of $m$ people from a pool of $n$ people for
your startup company, and from these $m$ people you want to choose $k$
to be the team managers.  You took 6.042, so you know you can do this
in
\[
\binom{n}{m}\binom{m}{k}
\]
ways.  But your CFO, who went to Harvard Business School, comes up with
the formula
\[
\binom{n}{k}\binom{n-k}{m-k}.
\]
Before you dump on your CFO or Harvard Business School, you decide to
check his answer against yours --- fortunately.

\begin{problemparts}

\problempart Give an algebraic proof that your CFO's formula agrees with yours.

\solution{
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}.
\end{eqnarray*} 
}

\problempart Now give what the Notes call a \emph{combinatorial argument}
proving this same fact.

\solution{Instead of choosing first $m$ from $n$ and then $k$ from
$m$, you could alternately choose the $k$ managers from the $n$ people
and then choose $m-k$ people to fill out the team from the remaining
$n-k$ people.  This gives you $\dbinom{n}{k} \dbinom{n-k}{m-k}$ ways
of picking your team.  Since you must have the same number of options
regardless of the order in which you choose to pick team members and
managers,
\[
\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.
\]
}

\end{problemparts}
\end{problem}
