BrainDen.com - Brain Teasers
• 0

# Combinations Problem

## Question

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.

## Recommended Posts

• 0

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

##### Share on other sites
• 0

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×