Proof by combinatorial argument

[ArcanaNoir]

Homework Statement

Give a combinatorial proof that [tex] (n-r)\binom{n+r-1}{r} \binom{n}{r}=n\binom{n+r-1}{2r} \binom{2r}{r} [/tex]

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 [itex] \binom{n}{r} [/itex] on the left side is choosing the r grad students. But then the [itex] \binom{n+r-1}{r} [/itex] 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 [itex] \binom{n}{k} \binom{k}{r}=\binom{n}{r} \binom{n-r}{k-r} [/itex].

 

[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 :)