Permutation of multiple sets of elements where adjacent elements are different.

Question

There are 5 red balls, 6 white balls and 7 black balls. How many ways can we arrange these ball in a line where the adjacent balls are in different color? And generalize the 5, 6, 7 into R, W, B.

Edit: Thanks for InterstellarProbe's answer. Here is a similar solution which is implemented with memo dfs. And its time complexity is $O(c^2*nr*nw*nb)$ where $c$ is the number of color and $nr$ is the number of red balls and so on.

from functools import lru_cache
from math import factorial
@lru_cache(None)
def dfs(c, nr, nw, nb):
    tr, tw, tb = sorted([nr, nw, nb], reverse=True)
    if tr - 1 > tw + tb: return 0
    if tr - 1 == tw + tb: return factorial(tw+tb) // factorial(tw) // factorial(tb)
    if c == 'W': nr, nw = nw, nr
    if c == 'B': nr, nb = nb, nr
    return dfs('W', nr, nw-1, nb) + dfs('B', nr, nw, nb-1)

def main(nr, nw, nb):
    return dfs('R', nr-1, nw, nb) + dfs('W', nr, nw-1, nb) + dfs('B', nr, nw, nb-1)
print(main(5, 6, 7))

Answer 1

I will give a hint, but not a complete answer.

Let $f(R,W,B)$ be the number of ways to order $R$ red balls, $W$ white balls, and $B$ black balls so that no two adjacent balls are of the same color.

Let $f(R,W,B;\text{Red})$ be the number of ways to order $R$ red balls, $W$ white balls, and $B$ black balls so that the first ball is Red.

Similarly for $f(R,W,B;\text{White})$ and $f(R,W,B;\text{Black})$.

We will try to build a recurrence relation.

$$f(R,W,B) = f(R,W,B;\text{Red})+f(R,W,B;\text{White})+f(R,W,B;\text{Black})$$

Let's try to break down each number further. If a sequence starts with red, then the balls after it must be a valid sequence of balls with one fewer red. However, it cannot start with red. This gives us the following three formulas:

$$f(R,W,B;\text{Red}) = f(R-1,W,B)-f(R-1,W,B;\text{Red})$$ $$f(R,W,B;\text{White}) = f(R,W-1,B)-f(R,W-1,B;\text{White})$$ $$f(R,W,B;\text{Black}) = f(R,W,B-1)-f(R,W,B-1;\text{Black})$$

And the following boundary conditions:

$$f(0,W,B) = \begin{cases}0, & |W-B|>1 \\ 1, & |W-B|=1 \\ 2, & |W-B|=0\end{cases}$$

and similarly for $f(R,0,B)$ and $f(R,W,0)$.

$$f(0,W,B;\text{Red}) = 0, f(R,0,B;\text{White}) = 0, f(R,W,0;\text{Black})=0$$

These four formulas give the recurrence relations that can be used to solve the problem. See what you can do with this (or another approach). If you still need help, get back to us and we can assist further.

Edit: Using an Excel program to evaluate this, I get $f(5,6,7) = 31632$.

Edit #2: Using this link: Permutations Calculator I got the same amount (31632).