Proof by combinatorial argument

[ArcanaNoir]

Homework Statement

Give a combinatorial proof that $$(n-r)\binom{n+r-1}{r} \binom{n}{r}=n\binom{n+r-1}{2r} \binom{2r}{r}$$

Homework Equations

The Attempt at a Solution

I interpreted the right side of the equation as:
There are n grad students and r undergrads. First, from the n grad students, choose a leader (Bob). There are n ways to do this. Then, from the n-1 remaining grads and r undergrads, choose 2r to be on a student committee. Then, choose r of the committee members to be on a subcommittee.

The left side is all kinds of sad. I did notice from the right side that there will be at least r grad students on the committee. So I want to say the $\binom{n}{r}$ on the left side is choosing the r grad students. But then the $\binom{n+r-1}{r}$ doesn't give you another r unique members. You get some arbitrary number from 0 to r for the new members. So you haven't chosen the same size committee on both sides.

I think there might be some sneaky adding and subtracting involved. I went to my professor's office hours and we looked at it for about 30-45 minutes but didn't ever get it straightened out.

 

[RUber]

What does it mean to give a combinatorial proof? Does it mean to not give a mathematical proof?

$(n - r) \frac{ ( n+ r - 1) !}{r!(n+r-r -1)! }\frac{ n !}{r!(n-r)! } = n \frac{ ( n+ r - 1) !}{2r!(n+r-2r -1)! }\frac{ (2r)!}{r!(2r-r)! }$

 

[ArcanaNoir]

What does it mean to give a combinatorial proof? Does it mean to not give a mathematical proof?

$(n - r) \frac{ ( n+ r - 1) !}{r!(n+r-r -1)! }\frac{ n !}{r!(n-r)! } = n \frac{ ( n+ r - 1) !}{2r!(n+r-2r -1)! }\frac{ (2r)!}{r!(2r-r)! }$

It means to argue by counting the same thing two different ways. For example choosing a committee and then a subcommittee versus choosing a subcommittee and then the remaining regular committee members would represent the equality $\binom{n}{k} \binom{k}{r}=\binom{n}{r} \binom{n-r}{k-r}$.

 

[Samy_A]

By your rule $\binom{n}{k} \binom{k}{r}=\binom{n}{r} \binom{n-r}{k-r}$, the right-hand side expression is the same as $n\binom{n+r-1}{r} \binom{n-1}{r}$

So we have to prove that $$(n-r)\binom{n+r-1}{r} \binom{n}{r}=n\binom{n+r-1}{r} \binom{n-1}{r}$$

Interpretation for the right-hand side expression: choose a president from the grad students ($n$), then form a committee of r grad students (not including the president) ($\binom{n-1}{r}$), then form another committee of r students (not including the president) ($\binom{n+r-1}{r}$).

Interpretation for the left-hand side expression: form a committee of r grad students ($\binom{n}{r}$), pick a president from the remaining n-r grad students ($n-r$), then form another committee of r students (not including the president) ($\binom{n+r-1}{r}$).

Not sure this is acceptable as a combinatorial proof, but note that the rule applied at the start of the argument also has a combinatorial proof. So at the very least it can be considered a two-step combinatorial proof.

 

[ArcanaNoir]

By your rule $\binom{n}{k} \binom{k}{r}=\binom{n}{r} \binom{n-r}{k-r}$, the right-hand side expression is the same as $n\binom{n+r-1}{r} \binom{n-1}{r}$

So we have to prove that $$(n-r)\binom{n+r-1}{r} \binom{n}{r}=n\binom{n+r-1}{r} \binom{n-1}{r}$$

Interpretation for the right-hand side expression: choose a president from the grad students ($n$), then form a committee of r grad students (not including the president) ($\binom{n-1}{r}$), then form another committee of r students (not including the president) ($\binom{n+r-1}{r}$).

Interpretation for the left-hand side expression: form a committee of r grad students ($\binom{n}{r}$), pick a president from the remaining n-r grad students ($n-r$), then form another committee of r students (not including the president) ($\binom{n+r-1}{r}$).

Not sure this is acceptable as a combinatorial proof, but note that the rule applied at the start of the argument also has a combinatorial proof. So at the very least it can be considered a two-step combinatorial proof.

Wowowowow! Thanks so much :)