Question 1164825: Prove each of the following identities using a counting argument. A purely algebraic proof will receive no credit.
(a):(n choose r) = n/n-r * (n-1 choose r), where n > r >= 0;
(b) (n choose m) (m choose r) = (n choose r) (n-r choose m-r), where n>=m>=r>=0
Answer by CPhill(2189)   (Show Source):
You can put this solution on YOUR website! To prove these identities using counting arguments (combinatorial proofs), we describe a scenario and count the number of ways to achieve a goal in two different ways. Since both ways count the same set of outcomes, the expressions must be equal.
---
### (a) Identity:
To make this easier to count, we rearrange the identity by multiplying both sides by :
**The Scenario:**
Suppose we have a group of people. We want to form a committee of people and designate one person from the remaining people to be the **"Official Observer"** (who is not on the committee).
* **Way 1 (Left Side):** First, choose the members of the committee from the available people. There are ways to do this. From the remaining people who did not make the committee, choose one person to be the Observer. There are ways to do this.
**Total:**
* **Way 2 (Right Side):** First, choose the Observer from the people. there are ways to do this. Now that the Observer is set aside, we need to choose the committee members from the remaining people. There are ways to do this.
**Total:**
Since both sides count the number of ways to choose a committee of and one separate Observer, the identity is proven.
---
### (b) Identity:
**The Scenario:**
Suppose you have students. You want to select a **Research Team** of students, and from that team, you want to select a **Leadership Sub-committee** of students.
* **Way 1 (Left Side):**
First, select the students for the Research Team from the total students. There are ways to do this. Then, from those selected students, choose of them to be the leaders. There are ways to do this.
**Total:**
* **Way 2 (Right Side):**
First, pick the leaders directly from the students. There are ways to do this. Now, you still need to fill out the rest of the Research Team. Since you already have leaders, you need more students to reach the team size of . You choose these students from the remaining students who were not picked as leaders.
**Total:**
Both sides count the number of ways to form a team of with a specific sub-group of leaders, thus the expressions are equal.
---
Would you like to see a similar proof for the **Vandermonde Identity** or perhaps the **Committee-Chair Identity**?
|
|
|
