In how many ways can we arrange $5$ blue, $3$ yellow and $3$ orange balls in a circle such that there are no adjacent balls of the same color?

Question

I read multiple approaches on how to solve this problem. However, I'm still not sure on how to do it as I am only acquainted with basic combinatorics. (clockwise and counterclockwise are considered the same)

My first approach was to calculate the total number of calculations and then get rid of the permutations that include two of equal color next to each other.

There are 11 Balls; Therefore the number of permutations should be: 11! = 39916800

Getting rid of the perms where two adjacent balls are equal in color is the part i can't figure out. (If this is even the right approach to this)

Answer 1

Hint:

Suppose we assume that all the same color balls are identical.

$B,B,B,B,B$--> Blue balls $Y,Y,Y$--> Yellow balls $O,O,O$-->Orange balls

$_B_B_B_B_B_$

There are $6$ blank spaces.

If the first space filled by $Y$ then last space should be filled by $O$. If the first space filled by $O$ then last space should be filled by $Y$.

First space can be filled in $2$ ways. (i.e) It is filled be either $Y$ or $O$.

So totally, first and last spaces can be filled in $2$ ways.

The remaining four spaces can be filled by {$Y$,$Y$,$O$,$O$}. Thus the remaining four spaces filled in $\frac{4!}{2!×2!}=6$ ways.

Thus overall the 6 blank spaces can be filled in $2×6=12$ ways.

Thus we have 12 linear permutation with one end start with $Y$ and ends with $O$ or one end start with $O$ and ends with $Y$. If we bend this line and merge the two ends we will get a cyclic arrangements which satisfying our requirements. Thus there are $12$ such an arrangement.

If CW and ACW are considered as same

Then required number $=12/2=6$.

Similarly you can check other possibilities. Like $B_ _ B_B_B_B_$ $B_ B_ _B_B_B_$ $B_ B_B_ _B_B_$ $B_ B_B_B_ _B_$ $B_ B_B_B_B_ _$ $_ _B_ B_B_B_B$ Etc.

Answer 2

Hint: The critical thing is that there is only one extra orange or yellow ball beyond what is needed to separate the blue ones. If we number the positions from $1$ to $11$ we can rotate the circle so the blue balls must go in $1,3,5,7,9$. Now we have defined the locations. How many ways to place balls in $10$ and $11$? Now pick the spaces for the remaining yellow balls.

Answer 3

UPDATE - the answer below considers fixed positions, with no symmetry. One of the comments led me to think about this as placing beads on a bracelet, which can be rotated and flipped, making my initial solution double-count many of the possibilities. My original answer suggested 11 positions in which to place the bloue balls, followed by $\binom{4}{2}\cdot 2$ remaining balls; if we make a bracelet instead, the 11 ways to place a blue ball reduces to 1, and the remaining result must be divided by two to account for mirror symmetry. Therefore, the answer is $\binom{4}{2}$.

My initial answer is below, which contains some thinking of how we arrive at $\binom{4}{2}$.

---

I have an answer, but to help and check, I wrote a little Python code to test it.

from itertools import permutations
bset = set()
for c in permutations(['b','b','b','b','b','y','y','y','o','o','o']):
    lc = list(c)
    # check 0 vs. 1, 1 vs. 2, ... n vs. 0
    if any(x[0]==x[1] for x in zip(lc, lc[1:]+[lc[0]])):
        continue
    bset.add(c)

print len(bset)

Borrowing from Avinash N's answer above, the intuition is first to place the blues into 5 of 11 positions. Now, the trick is to realize that 5 unadjacent blues require 10 slots, leaving one "double empty" slot that floats around. That is, we will get combinations where slots 1 and 2 are unoccupied, then slots 2 and 3, and so on, ending with slots 11 and 1 being empty. This is a total of 11 combinations.

Now place one of the other colors, using the "double empty" trick again. This time, we have 6 slots, all but two separated by a blue, so the first thing that comes to mind is $6 \choose 3$, but this is wrong because two of those slots are always the double empty that we cannot populate with the same color.

Instead, we have 4 safe, "interior" slots (bracketed by blues), and two unsafe double empty slots. For every way that 2 balls can go into the 4 safe slots, the one remaining ball can go into one of the two double empty slots, for a total of ${4 \choose 2} \cdot 2$ ways.

The slots for the third color are determined by the choices of the other two.

Combine the results of the blue and the not-blue to get the answer.