Prove by combinatorial argument.

Question

$$ \binom{n}{r} \binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k} $$

I was proving this equation, First i took L.H.S, then i open them with the help of Combinatorial Formula but, now I am Stuck, What to do next?

Answer 1

We want to choose $r$ persons among $n$ persons and assign $k$ of them as masters, and other $r-k$ persons as slaves. The left hand side is equal to choose $r$, persons first, and then select $k$ of them as master after that.

We can do it in another manner, as selecting first the $k$ masters among $n$ persons, and then select $r-k$ slaves from the remaining $n-r$ persons. It is equivalent to the right hand side. So they are equal.

Answer 2

HINT: You want a combinatorial proof, not an algebraic proof. Show that both sides count the ways to take $n$ pieces of paper, mark $r-k$ of them with the symbol $+$, and mark $k$ of the unmarked pieces with the symbol $\oplus$.

Answer 3

For the left hand side, you are computing the number of ways to choose a set with $r$ elements and then a set within with $k$ elements. For the right hand side you are choosing the set with $k$ elements first, then choosing the remaining $r-k$ elements in the set of size $r$ from the $n-k$ elements that remain.

Answer 4

Hint:You have a strip with $n$ slots and all the slots are colored white. Then you choose $r$ of the slots and you color them in gray,you can do it in $\binom{n}{r}$ ways, of those gray slots you will take $k$ of them and color them black in $\binom{r}{k}$. That is the left part by the multiplication principle. In the right part, do the same but first color them in black and then color the gray ones.