# Homework Help: Probability proof by combinatorial argument

1. Nov 26, 2008

### Proggy99

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

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. Nov 26, 2008

### Proggy99

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

3. Nov 26, 2008

### Dick

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'.

4. Nov 26, 2008

### e(ho0n3

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