# 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
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
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