Combinatorial Proof of a Simple Identity

Question

Consider the following identity: $\binom n r = \frac n r \binom {n-1} {r-1}$ where $n \ge r \ge 1$.

It's easy to supply an algebraic proof, but I'm looking for a combinatorial proof. I tried the following:

1. Denote by $S$ the set of $r$ objects that we are going to choose. We have $n$ ways to choose an object to put into $S$.
2. Now we choose $r - 1$ objects from the remaining $n - 1$ objects, giving $\binom {n-1} {r-1}$. By the multiplication principle, we have $n \binom {n-1} {r-1}$ ways to choose $r$ objects from $n$ objects.

Why doesn't the above proof work? Can anyone supply a clear combinatorial proof for the above identity?

EDIT: Clearly, I have overcounted by a factor of $r$.
EDIT2: I have written an answer to my own question. Let me know if there is anything wrong with it.

Answer 1

Rewrite the statement ${n\choose r}=\frac{n}{r}{n-1\choose r-1}$ into $r{n\choose r}=n{n-1\choose r-1}.$

To prove the latter statement, observe that $LHS$ first chooses an $r$-element set from $n$ elements and then picks an element, named the "representative", from the $r$-element set. Alternatively, $RHS$ first picks an element from the $n$ elements, and there are $n$ ways to do so. Then we choose $r-1$ elements from $n-1$ elements. Combined with the first picked representative, the $r-1$-element set forms a complete $r$-element set.

To sum up, $LHS$ picks an element after choosing a subset; conversely, $RHS$ picks an element before choosing a subset.

Answer 2

Let $S$ be a set of size $n$. $n \binom{n-1}{r-1}$ is the number of ways we may specify some $s \in S$ to miss out, and an $r-1$-subset from the remaining $n-1$ elements of $S \setminus \{s\}$. That is, it is the number of ways of choosing a "privileged $r$-subset" from the $n$ objects of $S$, where a "privileged $r$-subset" is a subset of size $r$ where we designate one of the elements to be a privileged element.

If we forget the fact that the element is privileged, we obtain a simple $r$-subset. How many ways can we obtain a particular $r$-subset from the privileged $r$-subsets? In precisely $r$ ways: because there are $r$ possible privileged elements to forget. Therefore $\frac{n}{r} \binom{n-1}{r-1} = \binom{n}{r}$.

More concretely, there is a bijection between {privileged $r$-subsets} and $\{\text{$r$-subsets} \} \times \{1, \dots, r \}$ given by "order the elements of the privileged $r$-subset, then create a 2-tuple by: the first coordinate is the $r$-subset without privilege, and the second coordinate is the position of the privileged element".

Answer 3

I am going to write an answer to my own question, inspired by James Pak's answer.

Consider the following situation:

I am a manager of a football association, and I want to set up a team of $r$ players from a pool of $n$ players, where $n \ge r \ge 1$. Additionally, I need one of the players in my team to be captain. In order to be fair to everyone, I make all my choices at random. There are (at least) two ways to set up such a team.

First way

I choose $r$ players at random from the pool of $n$ players to make up my team. Then, within the team, I randomly choose someone to be captain. In total there are $r \binom n r$ ways to carry out the whole sequence of events.

Second way

I decide that I want to choose a captain first, and then build the rest of the team around the captain. From the pool of $n$ players, I randomly elect someone to be captain of my upcoming team. Then from the remaining $n - 1$ players, I randomly choose $r - 1$ of them to make up the rest of the team. In total there are $n \binom {n-1} {r-1}$ ways to carry out the whole sequence of events.

In both ways I have achieved the exact same goal: to set up a team of $r$ players from a pool of $n$ players, and to choose one of the players in the team to be captain. Hence I conclude that $r \binom n r = n \binom {n-1} {r-1}$. Rearranging, I have $\binom n r = \frac n r \binom {n-1} {r-1}$.

Let me know if there's anything wrong with the above proof.