Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is probably a basic problem, but I'm having a really difficult time solving it.

There are ten red balls, ten green balls, ten blue balls, and ten white balls. Balls of the same color are considered equal. How many ways are there to select 24 balls, regardless of order? (Sorry if the question was phrased awkwardly, I translated it)

The question is supposed to be solved using the inclusion-exclusion principle.

I'd appreciate advice not only on how to solve this specific problem, but how to solve general inclusion-exclusion problems.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Let $ r + g + b + w = 24, r <= 10, g <= 10, b <= 10, w <= 10 $

Now let $ r' = r + 1$ and so on.

So $ r' + g' + b' + w' = 24 + 4 = 28$ and each is less than or equal to 11 and greater than or equal to 0.

Imagine we have 28 balls and we place three dividers between the balls. This divides them into four groups, one for $ r'$, $ g' $, $ b' $, and $w'$.

There are 27 slots in which to put dividers and we must place 3 of them. The number of divisions is $ {27 \choose 3}=2925 $.

But this is where inclusion-exclusion comes in. We must exclude each of the cases where one variable is $ > 11$ and then include when two are, and so on.

Let's say $r' = 12$. We have $ g' + b' + w' = 16 $. By the same argument, this is $ {15\choose2} $. There are four of those cases for each variable. We can go on all the way up to $r' = 25$. This reduces to:

$4{15\choose2} + 4{14\choose2} + 4{12\choose2} + 4{11\choose2} + ... + 4{2\choose2} = 4{16\choose3} $. The equal sign is by the hockey-stick identity.

Now what if $ r' = 12 = b' $? There are several of these cases where two variables are greater than 11. The logic is the same, you just must consider several cases. I'll leave it to you to finish.

At the end take $ {27 \choose 3} - 4{16\choose3} + (two > 11) $, by the principal of inclusion exclusion.

Note that three variables may not be greater than 11 because each variable must be >= 1.

This, unless there is some solution I am not seeing, is not a typical inclusion exclusions problem. It does use it, however it is only in the last step.

In general, an inclusions exclusion problem will ask: How many occurrences are such that at least x is/are in a certain state? The best thing is never to memorize a formula, but instead think critically about your counting. Count the number of ways that exactly 1 object is in a certain state. Think about how many times you just counted situations in which two objects are in a certain state and subtract off those states until they are counted exactly once. Then think about 3, and so on.

It is called inclusion exclusion because you are including some cases, and then excluding cases that are double counted, then including the ones that are undercounted, and so on.

EDIT: I should clarify. The reason for the adding one to r to get r', and so on, is that now each variable must be at least one. This simplifies the "divider" logic, although it is certainly not required to do so - it just takes a slightly different thought process.

share|improve this answer
    
While I appreciate the other answer, this one helped me more, not only to solve the specific problem but also of how to solve general problems. –  Daniel Jul 15 '12 at 19:39
    
Just to understand, the second inclusion will be of 6(4 1) + 6(3 1) + 6(2 1) + 6(1 1) - correct? Thanks! –  SyBer Feb 2 '13 at 20:02

I usually start with a smaller problem and look for a pattern to scale up to the goal.

Let's start with 2 balls of each color (2,2,2,2) and we want to draw 5 (roughly over half, just like 24/40).

On the first draw, all colors are equally likely, thus there are 4 possibilities (because all balls of the same color count the same).
On the second draw, I'm going to draw from a pool of 1,2,2,2 balls (one of the colors is lacking). There are still 4 possibilities here (although one is less likely than the other 3). However, since you said order doesn't matter, we've got to subtract off 4 chose 2 or 6 of those

So far, there are 4 * 4 - 16 = 10 possibilities, but you probably could have worked that out yourself. The next draw, things get tricky.

I could be at two different states (1,1,2,2) or (0,2,2,2). So, at this level are there 3 or 4 possibilities? Both. Of the 10 possibilities we have thus far, 4 are are the case in which we drew two of the same color and depleted that color leaving only 3 additional possiblities. For the other 6, they have 4 colors to pick from. So, at this point there are 4 * 3 + 6 * 4 = 36 combinations, but we have to account for duplicates again. The only ways we can have duplicates is either 2 of one color and 1 of another or 3 distinct colors. The latter is easy, 4 choose 3 or 4. The former is a bit more tricky but there are 4 choose 2 pairs of colors and in each pair the first color could be the one with 2 or the second color could be, thus 2 * (4 choose 2) or 12 duplications.

So, after three pulls we have 4 * 3 + 6 * 4 - 4 - 12 = 20 combinations. You may be thinking "ugh! This is all drudgework and we still have 2 more pulls to do!" Fear not. These sort of combinatorial problems usually have symmetry to them because you can just reverse the bag of balls and the table that you are setting the balls on, i.e. The combinations of 0 iterations are the same as n, 1 iterations is the same as n-1. Since we have calculated 3 steps, that's the same as 5, so we are done.

As far as scaling up your problem, you can easily parse through the first 10 steps, until you deplete a color. Then, go 6 more steps and stop because the work done at 16 will be the same as 24, which you are looking for.

Each iteration, find out how many total combinations there are for that step and then subtract off the duplicates. You may wish to try another small scale of 3 balls of each color, just to get the hang of all the tricks you may encounter at the scale of 10 balls of each color.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.