# Combination of three items with no adjacent items the same

I am looking for a closed expression for calculating the number of combinations of $n = n_1 + n_2 + n_3$ objects arranged in an ordered list, where there are $n_1$ $a$, $n_2$ $b$ and $n_3$ $c$, under the constraint that $a$ may not appear adjacent to $a$, $b$ not adjacent to $b$, and $c$ not adjacent to $c$.

If $n_1 = n_2 = n_3$, the following is an upper bound on the number of combinations:

$3$ ways of picking the first, and $2$ ways of picking all subsequent objects gives

$$3 \cdot 2^{n-1}$$

A solution only exists if $n_1$ is not greater than $1+n_2+n_3$ and similarly for $n_2$ and $n_3$

Thanks to @Byron Schmuland for pointing me to a general answer; the integral that needs to be evaluated looks a bit daunting.

Now I need a solution to the integral for three items like the one listed on page 9 of the paper cited in the answer for two items.

• Jair Taylor's answer here math.stackexchange.com/questions/129451/… gives the solution, not only for three, but also four, five, etc. – user940 Feb 18 '13 at 19:01
• Some MathJax tips for future reference: n_1 gives you index 1 on n; and \cdot is the multiplication dot. Putting an equation between double dollar signs centers it. – gnometorule Feb 18 '13 at 19:02
• Thanks for the link Byron Schmuland. My reading of that question is that it is for the case $n1=n2=n3$ only, which is useful as a tighter upper bound. I have a situation where the $n$'s are rarely equal. Thanks gnometorule – Derek Jones Feb 18 '13 at 19:11
• No, Taylor's solution does not assume $n_1=n_2=n_3$ and gives an explicit formula. – user940 Feb 18 '13 at 19:15
• The parameter to Taylor's equation is $k$, there is no $k_1$, $k_2$ and $k_3$ to support different numbers of each item. – Derek Jones Feb 18 '13 at 19:20

In addition to the formula linked above there is a nice generating function. The number of solutions with $i$ $a$'s, $j$ $b$'s and $k$ $c$'s is the coefficient of $a^ib^jc^k$ in $$\frac{1}{1 - \frac{a}{1+a} - \frac{b}{1+b} - \frac{c}{1+c}}.$$ This is a consequence of the beautiful "Carlitz-Scoville-Vaughan" theorem; see this MathOverflow question for an explanation.