Recurrence relation to find number of ways to cover $2×n$ chessboard with red and blue $2 \times 1$ tiles.

Question

Let a_n be the number of ways to cover a 2 x n chessboard using 2 x 1 red tiles and 2 x 1 blue tiles. Find a formula for a_n. Find a recurrence relation for a_n, with initial conditions.

Solution: given 2 x 1 red and blue tiles

If n =1 (2 x 1) then there are 2 ways to cover the chessboard. 1st: 1 red tile, 2nd 1 blue tile --> a₁ = 2

If n = 2 (2 x 2) then there are {r, r}, {b, b}, {r, b}, {b, r} --> a₂ = 4

If n = 3 (2 x 3) we have:

For red:

{r, r, r}, {r, b, r}, {r, r, b}, {b, r, r}

For blue:

{b, b, b}, {b, r, b}, {b, b, r}, {r, b, b}

--> a₃ = 8

If n = 4 ( 2 x 4) then

For red:

{r, r, r, r}, {r, b, r, r}, {r, r, b, r} {r, r, r, b}, {b, r, r, r}, {r, b, b, r}, {r, b, r, b},

For blue:

{b, b, b, b},{b, r, b, b}, {b, b, r, b} {b, b, b, r}, {r, b, b, b}, {b, r, r, b}, {b, r, b, r}.

--> a₄ = 14

At this point, I was unsure of my red and blue order. For example is {b, b, r} and {r ,b, b} the same thing? Am I overcounting the number of solutions for each a_n? Please help

Answer 1

Let $b_n$ be the number of tilings of $2 \times n$ with uncolored dominoes. Then \begin{align} b_1&=1\\ b_2&=2\\ b_n&=b_{n-1}+b_{n-2} &&\text{for $n\ge 3$} \end{align} which you can derive by conditioning on the last column. Note that $b_n$ satisfies the same recurrence as the Fibonacci numbers. Now $a_n = 2^n b_n$ because you have two choices for the color of each domino. So \begin{align} a_1&=2 b_1 = 2\\ a_2&=4 b_2 = 8\\ a_n&=2 a_{n-1} + 4 a_{n-2} &&\text{for $n\ge 3$} \end{align}

Answer 2

It’s clear that any time that you place a tile horizontally, you must pair it with another horizontal tile in the same two columns. Thus, any tiling consists of some combination of vertical tiles and pairs of horizontal tiles covering a $2\times 2$ square. If we look at just one row of such a tiling, it consists of $1\times 1$ and $1\times 2$ tiles covering a $1\times n$ board. It is well known that there are $F_{n+1}$ such tilings, where $F_n$ is the $n$-th Fibonacci number, and $F_0=0$. The other row will have the same sequence of $1\times 1$ and $1\times 2$ tiles, so ignoring color there are $F_{n+1}$ tilings of the $2\times n$ board with $1\times 2$ tiles. Any tiling of the $2\times n$ board by $1\times 2$ tiles uses $n$ tiles, each of which can be either red or blue, so there are $2^n$ combinations of colors and therefore $2^nF_n$ distinguishable tilings.