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!

Homework Help: Probability proof by combinatorial argument

  1. Nov 26, 2008 #1
    1. The problem statement, all variables and given/known data
    By a combinatorial argument, prove that for r [tex]\leq[/tex] n and r [tex]\leq[/tex] m,
    [tex](^{n+m}_{r})[/tex] = [tex](^{m}_{0})(^{n}_{r})[/tex] + [tex](^{m}_{1})(^{n}_{r-1})[/tex] + ... + [tex](^{m}_{r})(^{n}_{0})[/tex]

    2. Relevant equations

    3. The attempt at a solution
    I need some direction on how to start this problem. It is the only homework problem I am not sure of how to approach it.
  2. jcsd
  3. Nov 26, 2008 #2
    okay, so here is my attempt at beginning the solution

    The left side gives the number of ways that you can pick r total items from a set made up of two subsets of items with m and n items in each subset.

    The right side gives a series of permutations including how to pick no items from the first subset and all r items from the second, then how to pick 1 item from the first subset and the rest from the second, then 2 items from the first subset and the rest from the second, and continuing on until you are choosing all r items from the first subset and no items from the second.

    I am just not sure how to go about putting this in proof form
  4. Nov 26, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    So a choice on the right side must correspond to one of the choices on the left side and vice versa, right? I think that's exactly what you want to say, and I would call it a 'proof'.
  5. Nov 26, 2008 #4
    You can argue that in order to pick r items from m + n items, you have to pick x from the m items and r - x from the n items.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook