Proof by combinatorial argument

  • Thread starter ArcanaNoir
  • Start date
  • #1
768
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.
 

Answers and Replies

  • #2
RUber
Homework Helper
1,687
344
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)! } ##
 
  • #3
768
4
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].
 
  • #4
Samy_A
Science Advisor
Homework Helper
1,241
510
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. :smile:
 
Last edited:
  • Like
Likes RUber and ArcanaNoir
  • #5
768
4
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. :smile:

Wowowowow! Thanks so much :)
 

Related Threads on Proof by combinatorial argument

  • Last Post
Replies
2
Views
925
  • Last Post
Replies
1
Views
599
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
26
Views
4K
  • Last Post
Replies
2
Views
779
Top