How many ways to stack $n$ boxes of 4 colours so that no $2$ blue boxes are consecutive.

Question

Let $X_n$ denote the number of ways to stack red, white and blue and green boxes, find the ways to count the ways of stacking n boxes, with no consecutive blue boxes.

My attempt:

Let $X^R_n$ denote the number of ways of stacking n boxes with no consecutive blues, that have a red on top. Same for $X^W_n, X^B_n, X^G_n$.

Thus $X_n=X^R_n+X^W_n+X^B_n+ X^G_n$

Then $X^R_n=X_{n-1}$ as you have a n-string word with a defined last letter. With the same logic:

$X^R_n=X^W_n=X^G_n=X_{n-1}$.

For $X^B_n$ we have that the last character is B but the character before that can be only W, G or R so we get:

$X^B_n=X^R_{n-1}+X^W_{n-1}+ X^G_{n-1}=3X_{n-2}$

$$ \therefore X_n=3X_{n-1}+3X_{n-2} $$

Is this correct?

Answer 1

You only have to distinguish between blue and nonblue.

An admissible stack $S$ of height $n$ has a nonblue box on top or a blue box. In the first case $S'=S\setminus{\rm top\ box}$ is an admissible stack of height $n-1$, and in the second case $S''$ is an admissible stack of height $n-2$, and the $(n-1)^{\rm st}$ box is nonblue. It follows that $$X_n=3X_{n-1}+3X_{n-2}\ .$$ Furthermore one has $X_1=4$, $X_2=4^2-1=15$.

Answer 2

If I understand the question correctly, you have four sets of $n$ boxes in the colours red white blue and green. You can stack the red white and green boxes in $$\frac {(3n)!}{(n!)^3}$$ ways, and the remaining $n$ blue boxes can be inserted individually into the $(3n+1)$ gaps between these boxes (including the beginning and end) in $$\frac {(3n+1)!}{(2n+1)!n!}$$ ways. Then you multiply these together