Combinations Problem

[bubbled]

Express (M choose N) + (M choose N-1) as a single (X choose Y) in terms of M and N.

The problem is solvable using algebra, but the result can be explained using logic. I'm looking for that approach.

[k-man]

My attempt...

The answer is M+1 choose N.

The way to explain this logically seems to be easier if we reverse the question (at least it's easier for me). What is the difference (M+1 choose N) - (M choose N)? In other words the question is: How many combinations are introduced by choosing the same number of objects from a set that's larger by 1 object. The answer to this question is (M choose N-1) and here is why.

Say that we start with M white numbered balls and we choose N balls randomly. There are (M choose N) different results that we can have. Let's add a black ball and see how many new results we can have if we choose N balls from the new set that now includes the black ball. We have all the original results that don't include the black ball (M choose N) plus new results that include the black ball. Those that include the black ball have N-1 white balls and the number of those results is (M choose N-1).

 

 

[bubbled]

My attempt...

Hidden Content

 

 

Well done k-man. The explanation I heard from the lecturer was very similar:

 

Let's say you have a room with 30 pupils in it. You then figure out all the ways you can choose 10 students. For kicks, you also see how many ways you can choose 9 students. Now imagine the professor walks into the room, you now have 31 people in the room. If you were to add the professor to all the groupings of 9 students, combined with the earlier groupings of 30 choose 10, you have all the groupings of 31 choose 10.