Algorithms for 2-colouring a 2 x N matrix

Question

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions.

An example of all possible solutions for $N = 2$ is as follows:

(R)---(R)   (B)---(R)   (R)---(B)   (B)---(R)   (R)---(B)   (R)---(R)  (R)---(R)
 |     |     |     |     |     |     |     |     |     |     |     |    |     | 
 |     |     |     |     |     |     |     |     |     |     |     |    |     |     
(R)---(R)   (R)---(B)   (B)---(R)   (R)---(R)   (R)---(R)   (B)---(R)  (R)---(B)

I don't need to list all solutions, but what's a good algorithm for counting all solutions? For example, can we do it in $O(n)$ time or better?

Answer 1

One can view this problem as a dynamic programming problem with $3N$ subproblems.

Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red. By symmetry $RB(N)=BR(N)$.

We thus get the recurrences:

$$RR(N)=RR(N-1)+2BR(N-1)$$

$$BR(N)=RR(N-1)+BR(N-1)$$

Note that the total number of solutions for a $2\times N$ matrix is equal to $RR(N+1)$.

If one enters the first few terms (1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363,...) of this recurrence in OEIS one finds that it is A078057:

Expansion of $(1+x)/(1-2*x-x^2)$.

[...]

Number of length-$n$ strings of 3 letters $\{0,1,2\}$ with no two adjacent nonzero letters identical. The general case (strings of $L$ letters) is the sequence with g.f. $(1+x)/(1-(L-1)*x-x^2)$. - Joerg Arndt, Oct 11 2012

An algorithm which computes $RR(N)$ by evaluating the recurrence above can do so with $O(N)$ additions. The numbers can get as large as $\Omega(N)$-bit, so the complexity is $O(N^2)$.

Answer 2

I will show you how you can improve the computational complexity of Tom's solution. Let's rewrite his recursive relationship:

$$RR(N) = RR(N - 1) + 2BR(N - 1)$$ $$BR(N) = RR(N - 1) + BR(N - 1)$$

You can express this relationship using matrix multiplication.

$ \left( \begin{array}{cc} RR(N) \\ BR(N) \end{array} \right) % = \left( \begin{array}{cc} 1 & 2 \\ 1 & 1 \end{array} \right) % \left( \begin{array}{cc} RR(N - 1) \\ BR(N - 1) \end{array} \right) $

If we define $A$ s.t.:

$ A = \left( \begin{array}{cc} 1 & 2 \\ 1 & 1 \end{array} \right) $

We get that:

$ \left( \begin{array}{cc} RR(N) \\ BR(N) \end{array} \right) % = A \left( \begin{array}{cc} RR(N - 1) \\ BR(N - 1) \end{array} \right) % = A^2 \left( \begin{array}{cc} RR(N - 2) \\ BR(N - 2) \end{array} \right) = \dots % = A^{N - 1} \left( \begin{array}{cc} RR(1) \\ BR(1) \end{array} \right) $

$RR(1)$ and $BR(1)$ are known and multiplying $A^{N - 1}$ with the vector of these values requires $O(1)$ time, so all that you have to do is to calculate $A^{N - 1}$. This can be done in $O(logN)$ time if you use the exponentiation by squaring method. This method is known for calculating a power of a number fast but it can be applied in matrices too. It allows you to calculate the $k$-th power of a number or matrix of constant size in $O(logk)$ (we consider multiplications and additions as constant time operations), based on the binary representation of $k$. You can search for this method online as there are many resources about it. Another example where it is used is for calculating the $N$-th fibonacci number in $O(logN)$.

Note that this method doesn't require using square roots, which may raise problems in practical level (theoretically they are perfect), because of computers' limited floating point precision.

Answer 3

This answer fills the gap in the accepted answer by Tom van der Zanden, where the generating function is given by look-up magic without proper justification. This answer also produces the closed form of $RR(N)$.

Here are the recurrence relations.

$$\begin{align} RR(N)&=RR(N-1)+2BR(N-1) \tag{1}\\ BR(N)&=RR(N-1)+BR(N-1) \tag{2} \end{align}$$

Substituting $N+1$ for $N$ in equation (1) we have $$RR(N+1)=RR(N)+2BR(N) \tag{3}$$

(3) + 2$\times$(2) - (1) is $$ RR(N+1)+2BR(N)-RR(N)=RR(N)+2BR(N) + 2RR(N-1) + 2BR(N-1)-RR(N-1)-2BR(N-1),$$ which is $$ RR(N+1)=2RR(N)+RR(N-1)\tag{4}$$

Since $RR(1)=1$ and $RR(2)=3$, we can define $RR(0)=1$. The generating function of $RR(N)$ can be computed easily to be $$\frac{1+x}{1-2x-x^2}.$$

---

Let us deduce the close formula for $RR(N)$.

The characteristic equation of (4), $x^2-2x-1=0$ has two root, $1+\sqrt2$ and $1-\sqrt2$. Hence $RR(N)=c_1(1+\sqrt2)^N+c_2(1-\sqrt2)^N$ for some constant $c_1$ and $c_2$. Since $RR(0)=1$ and $RR(1)=1$, we get $c_1=\frac12$, $c_2=\frac12.$

$$RR(N)=\frac{(1+\sqrt2)^N+(1-\sqrt2)^N}2\text{ for all }N\ge0$$

---

Exercise. show that $$RR(N)=\left\lfloor\frac{(1+\sqrt2)^N+1}2\right\rfloor.$$

Answer 4

To complement Tom's answer: the coefficient of $x^n$ of the generating function $G(x)=\frac{1+x}{1-2x-x^2}$ is

$$[x^n]G(x)=\frac{\sqrt{2}+1}{2}\left(\frac{1}{\sqrt{2}-1}\right)^n-\frac{\sqrt{2}-1}{2}\left(\frac{-1}{\sqrt{2}+1}\right)^n$$

so you have a closed form for the number of colorings.

Note that this is the same as counting the number of (blue) independent sets in your graph. In general graphs this problem is #P-complete.