Exercise 800Combinatorics › Binomial coefficientsOlympiadAdded 3 Nov 2026

A combinatorial proof

#combinatorial proof#identity#binomial

Statement

Prove that $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$ .

Hint

Double count pairs of subsets $(A,B)$ with $|A|=k$ , $|B|=j$ , $B\subseteq A$ .

Show solutionHide solution

Solution

Count 1. Choose $A$ ( $\binom{n}{k}$ ), then $B\subseteq A$ of size $j$ ( $\binom{k}{j}$ ): $\binom{n}{k}\binom{k}{j}$ .

Count 2. Choose $B$ first ( $\binom{n}{j}$ ), then $A$ containing $B$ : choose $k-j$ more from $n-j$ remaining: $\binom{n-j}{k-j}$ . Total: $\binom{n}{j}\binom{n-j}{k-j}$ .

Conclusion. Both equal the count of $(A,B)$ pairs, so equal.

A combinatorial proof

Statement

Solution

More problems in Binomial coefficients