Proof by combinatorial argument

In summary, the equations state that there will be at least r grad students on the committee, but the left side doesn't give you another r unique members. The right side says that if you choose a president from the grad students, then form a committee of r grad students (not including the president), then form another committee of r students (not including the president), then the left side is the same as the right side.
  • #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.
 
Physics news on Phys.org
  • #2
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
RUber said:
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
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
Samy_A said:
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 to Proof by combinatorial argument

What is proof by combinatorial argument?

Proof by combinatorial argument is a method of proving a mathematical statement by using combinations or counting arguments. It involves using logical reasoning and mathematical principles to demonstrate the validity of a statement.

How is proof by combinatorial argument different from other proof methods?

Unlike other proof methods, such as direct proof or proof by contradiction, proof by combinatorial argument does not rely on algebraic manipulation or logical deduction. Instead, it relies on counting and examining all possible cases or combinations to show that a statement is true.

What types of problems can be solved using proof by combinatorial argument?

Proof by combinatorial argument is often used to solve problems in combinatorics, which involves counting and arranging objects or events. It can also be used to prove identities, inequalities, and other mathematical statements.

What are some common techniques used in proof by combinatorial argument?

Some common techniques used in proof by combinatorial argument include the pigeonhole principle, induction, and the method of double counting. These techniques involve carefully considering all possible combinations and using logical reasoning to prove a statement.

What are the advantages of using proof by combinatorial argument?

Proof by combinatorial argument can often provide elegant and intuitive solutions to complex mathematical problems. It also allows for the use of creative thinking and visualizing problems in different ways, which can be helpful in understanding and solving difficult problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
556
  • Precalculus Mathematics Homework Help
Replies
29
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
787
  • Calculus and Beyond Homework Help
Replies
1
Views
650
  • Calculus and Beyond Homework Help
Replies
1
Views
640
  • Calculus and Beyond Homework Help
Replies
3
Views
615
Replies
2
Views
300
  • Precalculus Mathematics Homework Help
Replies
7
Views
3K
Back
Top