# How many possible ways of stacking 12 red, 12 green, and 12 blue poker chips so that no blue is touching one another?

I need help for the following question:

How many possible ways of stacking $12$ red, $12$ green, and $12$ blue poker chips so that no blue chip is touching one another?

-

First stack the $24$ non-blue chips; in how may ways can you do this? Counting the position below the bottom non-blue chip and the position above the top non-blue chip, there are now $25$ positions in the stack into which you could put a blue chip. Since you don’t want two blue chips to touch each other, each blue chip has to go into a different one of these $25$ possible positions. How many ways are there to pick $12$ of the $25$ positions to accommodate the blue chips? Now how should you combine the results of these two calculations?

Added: This is a good example of a problem that can fairly easily be solved in more than one way; such problems are common in elementary combinatorics. El'endia Starman’s approach is perhaps a little less straightforward than this one, but its basic idea is, as noted, very useful, so it’s worth understanding both: the more tools you have at your disposal, the better.

-

I immediately recognized this as a version of the classic so-called "Hotdog Problem" in combinatorics. In this case, you can set this up like so:

_B_B_B_B_B_B_B_B_B_B_B_B_

In every inner blank, there must be at least one chip while the outside blanks may have none. This means that we have $12+12-11=13$ chips left that we can freely allocate to $13$ blanks. The number of ways that we can do this is $\binom{25}{12}=5200300$ (the $23$ comes from $11$ blanks plus $13$ free chips, minus one because the last item is determined by the others). We can further arrange the red and green chips amongst themselves, leading to $\binom{24}{12}=2704156$. These two orderings are independent of each other, so we can multiply them to get the total number of possible orderings. Thus, the answer is:

$\binom{25}{12}\binom{24}{12}=14062422446800$

The general method I used can be applied to basically every problem of this type, so be on the lookout for them. :)

-
The factor of ${24 \choose 13}$ is incorrect: the number of ways to distribute $n$ chips in $k$ blanks is ${{n+k-1} \choose {k-1}}$. – Brian M. Scott Jul 16 '11 at 5:43
@Brian: Yes, you are correct. I forgot the last item is determined by the other $n+k-1$ items. – El'endia Starman Jul 16 '11 at 5:44
But $n=k=13$ here - $13$ free chips for $13$ blanks - so it should be ${25 \choose 12}$. – Brian M. Scott Jul 16 '11 at 5:49
@Brian: ...oh right. This is why I almost never got a perfect score on a math test despite being good at the theoretical bits... :P – El'endia Starman Jul 16 '11 at 5:51

Hint : Consider the number of stackings in which the chips are allowed to touch each other first. Then subtract the number of stackings in which at least two blue chips touch, which is equivalent to consider 11 blue poker chips instead of 12.

-
Not necessarily $11$: at the other extreme, counting stackings in which all $12$ blue chips are together is like counting those with $12$ red and $12$ green chips and just $1$ blue chip. – Brian M. Scott Jul 16 '11 at 5:36
If you have a stacking in which the blue chips touch, then there exist at least two blue chips that touch ; up to permutation of the blue chips (which is admissible), the chips that touch can always be chosen to be for instance the first and the second ; thus you can consider, while counting stacking in which blue chips touch, that the "chip number 1 and chip number 2" are touching. The fact that more chips can touch each other is allowed in the counting if you count them well. =) – Patrick Da Silva Jul 16 '11 at 5:58
Simplify. Suppose that you have $2$ of each color, where the $2$ blue chips actually represent $3$ with at least two touching. The stack $RGBBRG$ corresponds to the single ‘bad’ stack $RGBBBRG$, but $RBGRBG$ corresponds to $RBBGRBG$ and $RBGRBBG$; how do plan to adjust for this in your calculation? – Brian M. Scott Jul 16 '11 at 6:14
I noticed my technique was crap but for some reason I can't edit my comment. +1 to yours. Usually the technique of removing stuff you don't want works but I just posted eagerly and didn't check by myself. – Patrick Da Silva Jul 16 '11 at 7:01