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

    Dick

    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