To prove the identity

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

where $n, r, k$ are nonnegative integers with $r \leq n$ and $k \leq r$, we use a combinatorial argument based on counting $r$-combinations and subsets of elements.

Explanation of the Identity

The left-hand side ($LHS$) and right-hand side ($RHS$) of the equation represent the number of ways to choose subsets under different perspectives:

1. LHS:

   • Choose an $r$-subset from $n$ elements ($\binom{n}{r}$).
   • Then, within this $r$-subset, choose a $k$-subset ($\binom{r}{k}$).

2. RHS:

   • Choose a $k$-subset from $n$ elements ($\binom{n}{k}$).
   • Then, choose $r-k$ additional elements from the remaining $n-k$ elements ($\binom{n-k}{r-k}$).

Proof Using Counting

LHS (Direct Counting)

1. Start by choosing an $r$-subset from $n$ elements. The number of ways to do this is $\binom{n}{r}$.
2. From this $r$-subset, choose $k$ elements. The number of ways to do this is $\binom{r}{k}$.
3. The total number of ways to perform this sequence of choices is the product: $\binom{n}{r} \binom{r}{k}.$

RHS (Alternative Counting)

1. Start by choosing a $k$-subset from $n$ elements. The number of ways to do this is $\binom{n}{k}$.
2. Then, choose $r-k$ additional elements from the remaining $n-k$ elements. The number of ways to do this is $\binom{n-k}{r-k}$.
3. The total number of ways to perform this sequence of choices is the product: $\binom{n}{k} \binom{n-k}{r-k}.$

Equivalence of Perspectives

Both the $LHS$ and $RHS$ describe the same counting problem: the total number of ways to form a subset of size $r$ from $n$ elements, ensuring that $k$ of those elements are selected first, and the remaining $r-k$ are chosen from the remainder. Therefore, the two expressions are equal.

Formal Proof Using Binomial Coefficients

The binomial coefficient is defined as: $\binom{n}{r} = \frac{n!}{r!(n-r)!}.$ Substituting this into both sides of the identity:

LHS:

$\binom{n}{r} \binom{r}{k} = \frac{n!}{r!(n-r)!} \cdot \frac{r!}{k!(r-k)!} = \frac{n!}{k!(r-k)!(n-r)!}.$

RHS:

$\binom{n}{k} \binom{n-k}{r-k} = \frac{n!}{k!(n-k)!} \cdot \frac{(n-k)!}{(r-k)!((n-k)-(r-k))!} = \frac{n!}{k!(r-k)!(n-r)!}.$

Since the simplified forms of $LHS$ and $RHS$ are identical, the identity is proved.

---

Key Points

1. Both sides count the number of ways to form subsets under different perspectives.
2. The identity relies on the fundamental definition of binomial coefficients and their combinatorial meaning.
3. The equivalence reflects a consistent relationship between subset selection processes.

---

Follow-up Questions

1. What are some real-world applications of this combinatorial identity?
2. How can this identity be extended to generalized combinatorics problems?
3. Can this proof be adapted for multinomial coefficients?
4. How does this identity relate to Pascal’s Triangle?
5. How does the proof change when additional constraints are placed on $r, k, n$?

Tip:

Visualizing combinatorial identities with small $n, r, k$ values can deepen understanding. For example, write out combinations for $n=5, r=3, k=2$.