In how many ways can $3$ red, $3$ blue, and $3$ green balls be arranged so that no two balls of the same colour are consecutive (up to symmetry)?

Make sequence of $9$ balls from 3 red, 3 blue, 3 green, in such a way that no two balls of the same colour are next to each other. In how many different ways can you do this? (symmetric arrangements must be counted only once).

To start with, all possible arrangements are $9! = 362880$.

Solution 1:

We have nine positions to fill with three blue, three green, and three red balls. We can fill three of the nine positions with blue balls in $\binom{9}{3}$ ways, three of the remaining positions with green balls in $\binom{6}{3}$ ways, and the remaining three positions with red balls in $\binom{3}{3}$ ways. Hence, the number of distinguishable arrangements of three blue, three green, and three red balls is $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!3!3!}$$ The factors of $3!$ in the denominator represent the number of ways balls of the same color can be permuted among themselves within a given arrangement since permuting balls of the same color among themselves does not produce an arrangement that is distinguishable from the given arrangement.

From these, we must exclude those arrangements in which there is at least one pair of adjacent balls of the same color.

A pair of adjacent balls of the same color: There are three ways to pick the color. We have eight objects to arrange, the block of two adjacent balls, the other ball of that color, and the other six balls. We have eight positions to fill.

Say the block consists of blue balls. Then we can fill three of those eight positions with green balls in $\binom{8}{3}$ ways, three of the remaining positions with red balls in $\binom{5}{3}$ ways, place the block in one of the two remaining positions in $2$ ways, and place the other blue ball in the final open position in one way. Hence, there are $$\binom{8}{3}\binom{5}{3}2! = \frac{8!}{3!3!}$$ such arrangements. Since there are three ways of selecting the color, there are $$\binom{3}{1}\frac{8!}{3!3!}$$ arrangements in which a pair of adjacent balls are of the same color.

Two pairs of adjacent balls of the same color: There are two cases.

Both pairs of adjacent balls are of the same color: This means that all three balls of that color are adjacent. Thus, we have seven objects to arrange, the block of three balls of the same color and the other six objects. Since there are three ways to select the color, the number of arrangements in which there are two pairs of adjacent balls of the same color is $$\binom{3}{1}\frac{7!}{3!3!}$$

Two colors in which there is a pair of adjacent balls of that color: There are $\binom{3}{2}$ ways to select the colors of the pairs. We have seven objects to arrange, the two blocks, the two single balls of those colors, and the three balls of the other color. Thus, there are $$\binom{3}{2}\frac{7!}{3!}$$ arrangements in which there are two colors in which there is a pair of adjacent balls of that color.

Three pairs of adjacent balls of the same color: There are again two cases.

Two pairs of adjacent balls of the same color and one pair of adjacent balls of a different color: There are three ways to pick the color in which there are two pairs of adjacent balls and two ways to pick the other color in which there is one pair of adjacent balls of that color. We have six objects to arrange, the block of three balls, the pair, the other ball of that color, and the three balls of the remaining color. Hence, there are $$\binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$ arrangements of this type.

Three colors in which there is a pair of adjacent balls of that color: We have six objects to arrange, the three blocks and the three individual balls. Since the objects are all distinct, there are $$6!$$ arrangements of this type.

Four pairs of adjacent balls of the same color: We again have two cases.

Two colors in which there are two pairs of adjacent balls of that color: There are $\binom{3}{2}$ ways to select the two colors. We have five objects to arrange, the two blocks of three adjacent balls of the same color and the three balls of the third color. Hence, there are $$\binom{3}{2}\frac{5!}{3!}$$ arrangements of this type.

One color in which there are two pairs of adjacent balls of that color and two other colors in which there is one pair of adjacent balls of that color: There are three ways to select the color with two pairs of adjacent balls of that color. We have five objects to arrange, the block of three balls, the two blocks of two balls, and the other two balls. Since the five objects are distinct, there are $$\binom{3}{1}5!$$ arrangements of this type.

Five pairs of adjacent balls of the same color: There must be two colors in which there are two pairs of adjacent balls of that color and there must also be a pair of adjacent balls of the third color. There are $\binom{3}{2}$ ways of selecting the two colors in which there are two pairs of adjacent balls of that color. We have four objects to arrange, the two blocks of three balls, the block of two balls, and the other ball of that color. Since the objects are distinct, there are $$\binom{3}{2}4!$$ arrangements of this type.

Six pairs of adjacent balls of the same color: There must be two pairs of adjacent balls of the same color in each of the three colors. Hence, we have three objects to arrange, a block of three blue balls, a block of three green balls, and a block of three red balls. Since these objects are distinct, there are $$3!$$ arrangements of this type.

By the Inclusion-Exclusion Principle, the number of distinguishable arrangements of three blue, three green, and three red balls in which no two balls of the same color are adjacent is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{8!}{3!3!} + \binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!} - \binom{3}{1}\binom{2}{1}\frac{6!}{3!} - 6! + \binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5! - \binom{3}{2}4! + 3!$$

This brings us to the question of symmetry. Notice that none of these $174$ arrangements can be a palindrome since for the two colors that do not occupy the middle position, there must be an odd number of balls of that color on one side of the middle ball and an even number of balls of that color on the other side of the middle ball. If we equate two arrangements that can be obtained through reflection, we are left with $87$ distinguishable arrangements of the balls.