Prove statement using formulas and then using a counting argument.

Question

Prove the following statement first by using formulas and second by using a counting argument. $$ \binom{n}{k}\binom{n-k}{j} = \binom{n}{j}\binom{n-j}{k} $$

Answer 1

Here is a counting argument. First, observe that the required equality may be reformulated as :

$$\binom n{n-k}\binom{n-k}j=\binom nj\binom{n-j}{n-j-k}$$

and even, with $p=n-k$ :

$$\binom np\binom pj=\binom nj\binom{n-j}{p-j}\tag{1}$$

Now consider a set of cardinal $n$, and count the numbers of ways we can form a pair of subsets $(A,B)$ with $card(A)=p$, $card(B)=j$ and $B\subset A$. This number is given by the LHS of $(1)$.

But it can also be viewed as the number of ways we can choose first $B$ and then complete this choice with $p-j$ elements outside of $B$. This leads to the RHS.