# In how many ways can $10$ blue and $10$ red balls be arranged so that no three consecutive balls are of the same color?

If there are $10$ blue balls and $10$ red balls. What are the total number of arrangements of these balls such that no three consecutive balls are of the same color?

I attempted this problem by subtracting unfavourable cases from total number of cases.

Unfavourable cases include those formed by permuting balls with a group of $3$ of $1$ color, and then those of another color. And then excluding those formed by permutations of balls with a group of $3$ red balls as well as a group of $3$ blue balls.

But this leaves many cases unattended.

• Any arrangement either starts with two balls of the same color or just one, followed by the same type of arrangement. This gives the recurrence relation for the Fibonacci numbers. So, the total number of arrangements is just twice the 20th Fibonacci number. – Rus May Feb 28 '18 at 21:25

As a brute force approach, divide up each color of balls into sets of size $1$ or $2$ each. Then count the possible number of orderings of each set and then for each partition consider the square of the number of orderings of that partition (if each color is divided into the same number of sets) and also the product with the number of orderings of the next smaller number of sets (if one color both starts and ends the sequence) then multiply by $2$ because either color could have started the sequence. $$\begin{array}{c|cccc}\text{Sets}&\text{Orderings}&\text{Same}&\text{Previous}&\text{Total}\\ \hline5&1&1&0&1\\ 6&15&225&15&240\\ 7&35&1225&525&1750\\ 8&28&784&980&1764\\ 9&9&81&252&333\\ 10&1&1&9&10\\ \hline&&&&4098\end{array}$$ So our final answer is $2\times4098=8196$. As confirmation, I offer total brute force:

program balls1
implicit  none
integer i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i
logical balls(20)
integer total, count
total = 0
count = 0
do i1=1,11
do i2=i1+1,12
do i3=i2+1,13
do i4=i3+1,14
do i5=i4+1,15
do i6=i5+1,16
do i7=i6+1,17
do i8=i7+1,18
do i9=i8+1,19
do i10=i9+1,20
balls = .FALSE.
balls([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]) = .TRUE.
count = count+1
do i = 1,18
if(all(balls(i:i+2)).OR..NOT.any(balls(i:i+2))) exit
end do
if(i>18) total=total+1
end do
end do
end do
end do
end do
end do
end do
end do
end do
end do
write(*,*) total,count
end program balls1


Output was

8196      184756