Problem 6 - A Gentle Introduction to the Art of Mathematics

Question

Prove the identity $$ \left(\begin{array}{l} n \\ k \end{array}\right) \cdot\left(\begin{array}{l} k \\ r \end{array}\right)=\left(\begin{array}{l} n \\ r \end{array}\right) \cdot\left(\begin{array}{l} n-r \\ k-r \end{array}\right) $$ combinatorially.

Step-by-Step Solution

Answer

The identity is proved by showing that both sides represent selecting \(r\) elements from a set of \(n\) elements, in two different sequences.

Step 1: Understanding Binomial Coefficients

The binomial coefficient \(\binom{n}{k}\) represents the number of ways to choose \(k\) elements from a set of \(n\) elements without regard to the order. It is calculated as: \[\binom{n}{k} = \frac{n!}{k!(n-k)!}\].

Step 2: Interpreting \(\binom{n}{k} \cdot \binom{k}{r}\)

The left-hand side of the identity is \(\binom{n}{k} \cdot \binom{k}{r}\). \(\binom{n}{k}\) represents selecting \(k\) elements out of \(n\), and \(\binom{k}{r}\) represents selecting \(r\) elements out of those \(k\). The combined process represents choosing \(r\) elements out of the \(k\) elements that were already chosen from the set of \(n\) elements.

Step 3: Interpreting \(\binom{n}{r} \cdot \binom{n-r}{k-r}\)

The right-hand side of the identity is \(\binom{n}{r}\ \cdot \binom{n-r}{k-r}\). \(\binom{n}{r}\) represents selecting \(r\) elements out of \(n\), and \(\binom{n-r}{k-r}\) represents selecting \(k-r\) elements from the remaining \(n-r\) elements after \(r\) elements have already been chosen. The combined process represents choosing \(r\) elements from \(n\) and then choosing \(k-r\) elements from the remaining \(n-r\) elements.

Step 4: Comparing the Two Combinatorial Interpretations

Both the left-hand side and right-hand side represent the same process of selecting a subset of elements from a total of \(n\) elements. On the left-hand side, the steps are done sequentially: first choosing \(k\) elements, and then choosing \(r\) elements from those. On the right-hand side, the steps are done differently but result in the same choices: first choosing \(r\) elements, and then \(k-r\) elements from the remaining \(n-r\).

Step 5: Conclusion

Since both sides represent the same selection process, the identity \(\binom{n}{k} \cdot \binom{k}{r} = \binom{n}{r} \cdot \binom{n-r}{k-r}\) is proved combinatorially.

Key Concepts

Combinatorics

Combinatorics is the field of mathematics dedicated to counting, arranging, and finding patterns in sets of elements.
At its core, it allows us to solve problems related to selection and arrangement of objects based on given constraints.
For instance, one of the most fundamental ideas in combinatorics is the binomial coefficient, represented as \(\binom{n}{k}\). This notation stands for the number of ways to choose \(k\) elements from a set of \(n\) elements without considering the order.
Several common problems—like determining the number of possible selections or arrangements—can be tackled using combinatorial techniques.
This makes combinatorics a powerful tool not only in mathematics but also in fields like computer science, statistics, and optimization.

Binomial Theorem

The Binomial Theorem is a key concept in combinatorics and algebra. It describes the expansion of powers of a binomial, which is an algebraic expression containing two terms.
For example, the binomial expression \( (a + b) \) can be expanded using the theorem as:
\((a+b)^n = \binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1}b^1 + \binom{n}{2}a^{n-2}b^2 + \cdots + \binom{n}{n}a^0 b^n\).
Each term in this expansion has a binomial coefficient \( \binom{n}{k} \), which can be interpreted combinatorially as the number of ways to choose \( k \) elements from a set of \( n \) elements.
The Binomial Theorem not only simplifies computation of binomial expansions but also establishes a deep link between algebra and combinatorics.
Its applications range from calculating probabilities in statistics to solving algebraic equations in higher mathematics.

Combinatorial Proof

A combinatorial proof establishes mathematical identities by interpreting them in terms of counting problems.
Unlike algebraic proofs, which rely on manipulations of expressions and equations, combinatorial proofs use logic and combinatorial reasoning to show that two expressions count the same set of objects in different ways.
In our exercise, we are asked to prove the identity \( \binom{n}{k} \binom{k}{r} = \binom{n}{r} \binom{n-r}{k-r} \) combinatorially.
This involves understanding that both sides count the number of ways to select \( r \) elements from \( n \), but through different intermediate steps.
On the left-hand side, we first select \( k \) elements from \( n \), and then \ r \ elements from those \ k \ chosen elements.
On the right-hand side, we first choose \ r \ elements from \( n \), leaving \ n-r \ elements.
Then, we pick \ k-r \ elements from those remaining.
Both sides ultimately describe the same selection process, proving the identity true.