1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by combinatorial argument

  1. Nov 24, 2015 #1
    1. The problem statement, all variables and given/known data
    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]

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Nov 24, 2015 #2


    User Avatar
    Homework Helper

    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)! } ##
  4. Nov 24, 2015 #3
    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].
  5. Nov 25, 2015 #4


    User Avatar
    Science Advisor
    Homework Helper

    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: Nov 25, 2015
  6. Nov 25, 2015 #5
    Wowowowow! Thanks so much :)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Threads - Proof combinatorial argument Date
Logic Proposition Proof Mar 16, 2018
Mathematical induction proof Jan 26, 2018
Is this proof valid? Jan 8, 2018
Complex Proof Dec 1, 2017
Disjunctive Normal form to Combinatorial Circuit Apr 13, 2016