- #1

ArcanaNoir

- 779

- 4

## 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.