Given a board of size $1 \times n$,in how many this board can be colored with the colors white,yellow,blue assuming the number of blue cells is even

Question

Given a board of size $1 \times n$,in how many this board can be colored with the colors white,yellow and blue assuming the number of blue cells is an even number.

---

My try:

Given a board of size $1 \times n$,then there are two possibilities for the color of the first cell:

• If the first cell is blue then the it's needed to find another cell to color it with the blue color ,this can be done in $n-1$ ways and for each one of these choices there are $b_{n-2}$ ways to color the remaining $1 \times (n-2)$ board with the colors yellow,white and blue assuming the number of blue cells is an even number.

• If the first cell is yellow or white then the remaining $1 \times (n-1)$ board can be colored in $b_{n-1}$ ways assuming the restriction on the number of blue cells is satisfied.

Gathering these cases follows:

$$b_n=(n-1)b_{n-2}+2b_{n-1}$$

With $b_0=1$ and $b_1=2$ as initial conditions.

Calling $G(x)=\sum_{k\ge 0}^{} b_k x^k$,omitting some elementary calculations follows:

\begin{align*} G(x)&=\frac{-1}{\left(n+1\right)^{2}x^{2}+2x-1}\\ &=\frac{-1}{\left(n+1\right)^{2}}\frac{1}{(x-a)(x-b)}\\ &=\frac{1}{\left(n+1\right)^{2}(a-b)}\left(\frac{1}{a-x}-\frac{1}{b-x}\right)\\ &=\frac{1}{\left(n+1\right)^{2}(a-b)}\left(\frac{1}{a}\frac{1}{1-\frac{x}{a}}-\frac{1}{b}\frac{1}{1-\frac{x}{b}}\right)\\ & \end{align*}

From which we conclude: \begin{align*} b_n=\left[x^{n}\right]G\left(x\right) &=\frac{1}{\left(n+1\right)^{2}(a-b)}\left(\left(\frac{1}{a}\right)^{n+1}-\left(\frac{1}{b}\right)^{n+1}\right)\\ \end{align*}

Where $$a=\frac{-1+\sqrt{n+2}}{n+1},b=\frac{-1-\sqrt{n+2}}{n+1}$$

But the closed form does not coincide with the recurrence that I've found.(I only want the question to be solved using recurrence relations.)

Answer 1

Let $a_n$ be the number of colorings with an odd number of blues, and $b_n$ be the number of colorings with an even number of blues.

Then $$a_n=b_{n-1}+2a_{n-1}\tag1$$ because to get an odd number of blues, we can either color the first square blue and color the remaining $n-1$ squares with an even number of blues, or color the first square white or yellow, and then color the remaining squares with an odd number of blues. Similarly, we have $$b_n=a_{n-1}+2b_{n-1}\tag2$$ From $(2)$, $a_{n-1}=b_n-2b_{n-1}$, and substituting this in $(1)$ gives $$b_{n+1}-4b_n+3b_{n-1}=0,$$ which can be solved in the usual manner.

Answer 2

Roughly, half of the colorings have an even number of blue cells. To make this precise, for each coloring, $C$, define the "mate" of $C$ to be the coloring you get when you find the leftmost cell of $C$ which is white or blue, and change it to be blue or white. Every coloring is given a mate, except for the single all-yellow coloring which has no blue or white cells. However, the remaining $3^n-1$ colorings are divided into pairs of mates. Furthermore, in each pair of mates, exactly one coloring has an even number of blues. Therefore, the number of colorings with an even number of blues is $$ \frac{3^n-1}2+1. $$

Answer 3

Consider the expansion of $(w+y+b)^n$. Then each term represents a pattern on the board in a natural way.

Now let $w=y=1, b=-1$. Then each pattern with an even number of Blues counts $+1$ and each pattern with an odd number of Blues counts $-1$.

Since $(1+1-1)^n=1$, there is one more 'even' pattern than 'odd'.

Hence there are $\frac {3^n+1}{2}$ 'even' and $\frac {3^n-1}{2}$ 'odd'.