Computing binomial coefficients

Question

Compute from Left-Side: $$ {n \choose p} {n-p \choose k-p} = {n \choose k-p \quad p \quad n-k } = {n \choose k} {k \choose p}$$

So i started computing until:

$$ ={n \choose p} {n-p \choose k-p}$$ $$=\left(\frac{(n!)}{(p!) (n-p)!}\right) \left(\frac{(n-p)!}{(k-p)! ((n-p)-(k-p))!}\right) $$ $$=\left(\frac{(n!)}{(p!) (n-p)!}\right) \left(\frac{(n-p)!}{(k-p)! (n-k)!}\right) $$

and this is where i get stuck. How can i continue breaking this down until it equals the right-side? What algebraic definitions or binomial theorems am i not understanding? help?

Answer 1

You can have $$\frac{n!}{p!\color{red}{(n-p)!}}\cdot\frac{\color{red}{(n-p)!}}{(k-p)!((n-p)-(k-p))!}=\frac{n!}{p!(k-p)!(n-k)!}.$$ Now, mutiplying this by $\frac{k!}{k!}\ (=1)$ gives $$\frac{n!}{p!(k-p)!(n-k)!}\cdot\frac{k!}{k!}=\frac{n!}{k!(n-k)!}\cdot\frac{k!}{p!(k-p)!}=\binom{n}{k}\binom{k}{p}.$$

Answer 2

You need to cancel out $(n-p)!$

$\left(\frac{(n!)}{(p!) (n-p)!}\right) \left(\frac{(n-p)!}{(k-p)! (n-k)!}\right)$

$=\left(\frac{(n!)}{(p!) }\right) \left(\frac{1}{(k-p)! (n-k)!}\right)$

$=\left(\frac{(n!)}{(p!)(k-p)! (n-k)!}\right)$

$ = {n \choose k-p \quad p \quad n-k }$

And

$\left(\frac{(n!)}{(p!)(k-p)! (n-k)!}\right)$

$=\left(\frac{(n!)}{(k!) (n-k)!}\right) \left(\frac{(k!)}{(p!)(k-p)!}\right)$

$ = {n \choose k} {k \choose p}$

Answer 3

Using the "subset of a subset" identity $$\binom ab\binom bc=\binom ac\binom {a-c}{b-c}$$ (which can be proven by expansion but also makes sense logically) and putting $a=n, b=k,c=p$,we have $$\begin{align} \text{RHS}&=\binom nk\binom kp\\ &=\binom np\binom {n-p}{k-p}=\text{LHS}\quad\blacksquare \end{align}$$