There are items comprising of red cubes, blue cubes, and balls; how many ways can 3 red cubes, 4 blue cubes and 8 balls be arranged in a line so that:

No three cubes are consecutive
No three balls are consecutive
No two red cubes are next to one another
No two blue cubes are next to one another

How do we go about finding a general formula for \(r\) red cubes, \(b\) blue cubes and \(c\) balls ?

The answer lies in forming a directed graph / Finite Automaton, as we have seen it in one of the previous posts.

Instead of filling in the number of ways, we use the variable names as weights for the valid transitions.

Hence, we can directly solve for the general case by using the following adjacency matrix:

\begin{equation*} \displaystyle \begin{array}{|l|rrrrrr|}\hline & \mathrm{I} & \mathrm{R} & \mathrm{B} & \mathrm{C} & \mathrm{BR} & \mathrm{CC} \\ \hline \mathrm{I} & 0 & r & b & c & 0 & 0 \\ \mathrm{R} & 0 & 0 & 0 & c & b & 0 \\ \mathrm{B} & 0 & 0 & 0 & c & r & 0 \\ \mathrm{C} & 0 & r & b & 0 & 0 & c \\ \mathrm{BR} & 0 & 0 & 0 & c & 0 & 0 \\ \mathrm{CC} & 0 & r & b & 0 & 0 & 0 \\ \hline \end{array} \end{equation*}

which is for the constraints that there's no \(RR, BB, RBR, BRB\) or \(CCC\).

Therefore, for 15 items, we compute

\begin{equation*} \displaystyle \left(\begin{array}{rrrrrr} 0 & r & b & c & 0 & 0 \\ 0 & 0 & 0 & c & b & 0 \\ 0 & 0 & 0 & c & r & 0 \\ 0 & r & b & 0 & 0 & c \\ 0 & 0 & 0 & c & 0 & 0 \\ 0 & r & b & 0 & 0 & 0 \end{array}\right)^{15} \end{equation*}

and extract \([c^8 b^4 r^3]\) from the sum of the first row, which is \(11394\).

We may also compute the characteristic polynomial of the matrix to get the structure of its multivariate recurrence relation:

\begin{equation*} \displaystyle x^6 - (bc + cr)x^4 - (bc^2 + 2bcr + c^2r)x^3 - 2bc^2rx^2 = 0 \end{equation*}

which is just like the characteristic equation of a recurrence relation, which is:

\begin{equation*} \displaystyle f_{b,c,r} = f_{b-1,c-1,r}+f_{b,c-1,r-1}+f_{b-1,c-2,r}+f_{b,c-2,r-1}+2 \left(f_{b-1,c-1,r-1}+f_{b-1,c-2,r-1}\right) \end{equation*}

and set the required boundary conditions.

Computing the regular expression from the minimized DFA gives us the following multivariate generating function:

\begin{equation*} \displaystyle G(r,b,c) = \frac{\left(1+c+c^2\right)\left(1+b+r+2br\right)}{1-c\left(1+c\right)\left(b+r+2br\right)} \end{equation*}

Reference:

Putting objects in a line