4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)$.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.$$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.