Colored Blocks Factorial

I was given the following problem:

A bag contains 14 red blocks, 10 white blocks and 12 blue blocks. How many different 19 block sets can be created from the collection in the bag? Two block sets are considered different if they differ in the number of blocks of some particular color.

How would I go about solving this? I'm not sure how to begin since there are many more blocks than the number of items in the desired set, and there's also the different colors. Any guidance would be appreciated.

Solution 1:

This is a stars-and-bars problem with extra conditions. You’re looking for the number of integer solutions to the equation $r+w+b=19$ subject to the conditions $0\le r\le 14$, $0\le w\le 10$, and $0\le b\le 12$. Here $r,w$, and $b$ stand for the numbers of red, white, and blue blocks, respectively, in your $19$-block set. If we had at least $19$ blocks of each color, there would be $$\binom{19+3-1}{3-1}=\binom{21}2=210$$ solutions and hence the same number of possible $19$-block sets. However, we have to subtract from this the solutions that make at least one of $r,w$, and $b$ too large. (This sort of calculation is an inclusion-exclusion calculation.)

How many solutions have $r>14$? Those all have $r\ge 15$, so if we set $r'=r-15$, there is an obvious bijection between solutions of $r'+w+b=4$ in non-negative integers and solutions of $r+w+b=19$ in non-negative integers with $r\ge 15$. The stars-and-bars calculation tells us that $r'+w+b=4$ has $$\binom{4+3-1}{3-1}=\binom62=15$$ solutions in non-negative integers, so $15$ of the original $210$ solutions have to be ruled out because they use too many red blocks.

Now do the same thing to see how many of the $210$ unrestricted solutions use too many white blocks and how many use too many blue blocks; both of those numbers will have to be subtracted from $210$ as well.

Finally, note that in principle a solution of $r+w+b=19$ might violate more than one of the upper bounds. In this problem that’s not possible, so you’ll be done after you finish the previous step, but if it were possible, you’d have more work to do. A solution violating two of the upper limits, for instance, would have been subtracted twice, once for each violation, so you’d have to add back in all solutions that violate two conditions. Then if there were some solutions that violated all three conditions, you’d find that a further correction was necessary: you’d have to subtract them. For more on this see the inclusion-exclusion link above.

This earlier answer to a similar problem also includes a fair bit of detail.