In how many ways can R red, B blue, and G green balls be arranged so that no two balls of the same colour are consecutive?

Question

Given R red balls, B blue balls and G green balls, how many ways are there to arrange them on a straight line such that no two balls of the same color are next to each other?

In essence, my question is a generalization of this question.

In the above post, the accepted answer enumerates all cases in which there is a violation of the restriction. As such, it may not be so easy to compute if the quantity of each ball is large (e.g. 100 of each ball) as we have to compute each case manually.

I wish to ask if there is a generalized formula/expression that can answer the same question for R red balls, B blue balls and G green balls (It doesn't matter even if the expression is not in closed-form because I want to compute this on a computer).

Could someone please advise me?

Answer 1

You can have a look here for a number of approaches.

Choose the one that suits you best.

Answer 2

Answer

If $t=R+G+B$ then the number of arrangement with no adjacent identical colour balls is

$$\sum_{k=0}^{t}(-1)^{k}\sum_{k_R+k_B+k_G=k}\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}$$

Explanation

For set of red balls $\{r_1,r_2\ldots,r_R\}$, blue balls $\{b_1,b_2\ldots,b_B\}$, and green balls $\{g_1,g_2\ldots,g_G\}$ call an "adjacency" of an arrangement of the balls a single occurrence of equal colour adjacent balls. Then, if $A_k$ is the sum of intersection of sets of arrangements with at least $k$ adjacencies, then by inclusion-exclusion the required count is

$$\sum_{k=0}^{t}(-1)^k|A_k|\, .\tag{1}$$

So it simply remains to show that $|A_k|$ is the inner summation in the answer.

Consider that, for any set $S$ of identical coloured balls, there are

$$\binom{|S|-1}{k_{|S|}}\frac{|S|!}{(|S|-k_{|S|})!}\tag{2}$$

ways to place elements into $|S|-k_{|S|}$ blocks of unordered elements with $k_{|S|}$ adjacencies: Adjacent elements within blocks contribute an adjacency but those adjacent elements in neigbouring blocks do not e.g. $(r_1,r_2,r_3)(r_4,r_5)$ has adjacency $r_1,r_2$ but not $r_3,r_4$ and is different from $(r_2,r_1,r_3)(r_4,r_5)$ but the same as $(r_4,r_5)(r_1,r_2,r_3)$. The elements adjacent inside the blocks contribute exactly $1$ adjacency, so our examples here each have $3$ adjacencies.

To see $(2)$, notice there are $\binom{|S|-1}{k_{|S|}}$ ways to put $|S|$ identical balls in $|S|-k_{|S|}$ block with each block containing at least $1$ ball. Then there are $|S|!$ ways of labelling those balls. But we must divide out the repeats, which is simply the number of ways of arranging $|S|-k_{|S|}$ blocks i.e. divide by $(|S|-k_{|S|})!$, hence $(2)$.

For $k=k_R+k_B+k_G$ adjacencies there are $\binom{R-1}{k_R}\frac{R!}{(R-k_R)!}$ ways of forming $R-k_R$ red blocks with $k_R$ adjacencies, $\binom{B-1}{k_B}\frac{B!}{(B-k_B)!}$ ways of forming $B-k_B$ blue blocks with $k_B$ adjacencies and $\binom{G-1}{k_G}\frac{G!}{(G-k_G)!}$ ways of forming $G-k_G$ green blocks with $k_G$ adjacencies. There are then $(R+G+B-(k_R+k_B+k_G))!=(t-k)!$ ways of arranging all $t-k$ blocks, giving

$$\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{R!B!G!(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}$$

total arrangements with at least $k$ adjacencies and at least $k_R$ red contributions, at least $k_B$ blue contributions and at least $k_G$ green contributions.

For each $k$ this must be summed over possible values of $k_R,k_B$ and $k_G$. Thus the total number of arrangements of those sets with no equal colour adjacencies is, by $(1)$

$$\sum_{k=0}^{t}(-1)^{k}\sum_{k_R+k_B+k_G=k}\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{R!B!G!(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}\, ,$$

but if we want to treat red balls as identical, blue balls as identical and green balls as identical then we must divide out the arrangements of those $R!B!G!$ giving our answer at the top.

So, let's use the example of $R=B=G=3$ then we have:

$$\begin{multline}\frac{9!}{3!^3}-3\binom{2}{1}\binom{2}{0}^2\frac{8!}{2!3!^2}+\left(3\binom{2}{2}\binom{2}{0}^2\frac{7!}{1!3!^2}+3\binom{2}{1}^2\binom{2}{0}\frac{7!}{3!2!^2}\right)\\-\left(6\binom{2}{2}\binom{2}{1}\binom{2}{0}\frac{6!}{1!2!3!}+\binom{2}{1}^3\frac{6!}{2!^3}\right)+\left(3\binom{2}{1}^2\binom{2}{2}\frac{5!}{2!^21!}+3\binom{2}{2}^2\binom{2}{0}\frac{5!}{1!^23!}\right)\\-3\binom{2}{2}^2\binom{2}{1}\frac{4!}{1!^22!}+\binom{2}{2}^3\frac{3!}{1!^3}=174\end{multline}$$

---

Note that this method is really just the Laguerre Polynomial method in disguise but I thought it might be instructive to present it this way as it sheds some light on the underlying combinatorics.