# Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following:

If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then

$$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$.

I did the following steps:

\begin{align} \require{cancel} \binom{n}{m}\binom{m}{k} &= \binom{n}{k}\binom{n-k}{m-k} \\ \frac{n!}{m!(n-m)!}\cdot \frac{m!}{k!(m-k)!} &= \frac{n!}{k!(n-k)!}\cdot \frac{(n-k)!}{(m-k)!(n-k-m+k)!}\\ \frac{n!}{\cancel{m!}(n-m)!}\cdot \frac{\cancel{m!}}{k!(m-k)!} &= \frac{n!}{k!\cancel{(n-k)}!}\cdot \frac{\cancel{(n-k)}!}{(m-k)!(n-k-m+k)!} \\ \frac{n!}{k!(n-m)!(m-k)!} &= \frac{n!}{k!(n-m)!(m-k)!} \end{align}

The question is: is my proof correct? Are all my steps valid?

Thanks

• Maybe it is just me, but I am little confused of how you went in one step from $(m-k)!(n-k-m+k)!$ to $(n-m)!(m-k)!$ – imranfat Mar 20 '14 at 19:15
• @imranfat, $(n−k−m+k)!=(n-m)!$. – DKal Mar 20 '14 at 19:16
• Ok, I see it now, there has been a complete brainfart in my head going on... – imranfat Mar 20 '14 at 19:24
• Thanks for the edit Umberto! – Jeel Shah Mar 20 '14 at 19:32

It is correct!

An other way to prove this is the following:

$$\binom{n}{m}\binom{m}{k} = \frac{n!}{m!(n-m)!} \frac{m!}{k!(m-k)!}= \frac{n!}{(n-m)!} \frac{1}{k!(m-k)!}=\frac{n!}{k!} \frac{1}{(m-k)!(n-m)!}=\frac{n!}{k!(n-k)!} \frac{(n-k)!}{(m-k)!(n-m)!}=\binom{n}{k}\frac{(n-k)!}{(m-k)!((n-k)-(m-k))!}=\binom{n}{k} \binom{n-k}{m-k}$$

• The back of the book suggested that I use the following fact $\binom{n+1}{k+1} = \frac{n+1}{k+1}\binom{n}{k}$. How would I use that? Also, on the second last portion i.e. $(n-m)!$ going to $((n-k)-(m-k))!$ is that because we have $n = n-k$ and $m=m-k$? – Jeel Shah Mar 20 '14 at 19:31
• As regards the second question: $$(n-m)!=(n-m+0)!=(n-m+k-k)!=(n-k-m+k)!=((n-k)-(m-k))!$$ – Mary Star Mar 20 '14 at 19:34
• To use the relation $$\binom{n+1}{k+1}=\frac{n+1}{k+1} \binom{n}{k}$$ you could do the following: $$\binom{n}{m}=\frac{n}{m} \binom{n-1}{m-1}=...=\frac{n \cdot ... \cdot (n-k+1)}{m \cdot ... \cdot (m-k+1)} \binom{n-k}{m-k}=\frac{\frac{n!}{(n-k)!}}{\frac{m!}{(m-k)!}} \binom{n-k}{m-k}=\frac{\frac{n!}{k!(n-k)!}}{\frac{m!}{k!(m-k)!}} \binom{n-k}{m-k}= \frac{ \binom{n}{k} }{ \binom{m}{k} } \binom{n-k}{m-k}$$ So $$\binom{n}{m} \binom{m}{k}= \frac{ \binom{n}{k} }{ \binom{m}{k} } \binom{n-k}{m-k} \binom{m}{k}= \binom{n}{k} \binom{n-k}{m-k}$$ – Mary Star Mar 20 '14 at 22:41

You appear to do this in a non-standard way, but it looks alright (reading the equations from top to bottom instead of left to right).

Ever thought of a combinatoric proof?

Looks correct to me. Alternatively, you can give a combinatorial proof: both sides of the equation count the number of options to choose subsets $K\subseteq M\subseteq N$, where $N$ is a set of $n$ elements, $M\subseteq N$ is a subset of $m$ elements, and $K\subseteq M$ is a subset of $k$ elements. On the LHS you choose $M$ and then choose $K$ in $M$. On the RHS you choose $K$ in $N$ first, and then determine $M$ by choosing $m-k$ more elements from $N\setminus K$.