Recursion: In how many ways we can tile a rectangle with size of $1\times 10$ without two adjacent red floor tiles?

Question

This is the question:

We have unlimited floor tiles in the colors red or blue. Every color comes in the size of $1\times 1$ or $1 \times 2.$

In how many ways we can tile a rectangle with size of $1\times 10$ without two adjacent red floor tiles? What is the recursion formula for that problem and that are the start conditions?

---

I have tried to think about a solution like this:

• for rectangle size of $1 \times 1$ we have $2$ options: red or blue $1 \times 1$ floor tile

• for rectangle size of $1\times 2$ we have $3$ options: red & blue $1 \times 1,$ $2$ blue $1 \times 1$ or $1$ blue $1 \times 2$

But later then I got stucked with comming up with a solution to Typical Polynomym

Answer 1

Notation: $R(1,1)$ is a $1\times 1$ red tile, $R(1,2)$ is a $1\times 2$ red tile and so on.

There are two reasons for which the question seems awkward.

1. What does how many ways mean? More precisely, when tiling a $1\times 2$ rectangle, $R(1,1)+B(1,1)$ is the same as $B(1,1)+R(1,1)$? Looking at your count, it seems that you would like to consider them as representing one tiling. My answer below considers them as being distinct. To state it differently: I consider no symmetry that identifies two tilings.

2. Your example for a $1\times 2$ rectangle is incorrect whatever way of counting you consider; you forgot the $R(1,2)$ construction.

A solution sketch. A tiling for a $1\times n$ rectangle is considered as having, either a final $R(1,i)$ or a $B(1,i)$ tile. Denote $r_n$ the number of tiling ending with a red one, and $b_n$ the number of those ending with a blue one. We need to determine these two sequences.

We have, after some moments of thought about the final tile, $b_n=b_{n-1}+r_{n-1}+b_{n-2}+r_{n-2}$ and $r_n=b_{n-1}+b_{n-2}$. Moreover, $b_1=1$ and $b_2=3$, and $r_1=1$ and $r_2=2$.

To have our count, it is sufficient to determine $(b_n)_n$. But using the two recurrent relations, $b_n=b_{n-1}+2b_{n-2}+2b_{n-3}+b_{n-4}$ with the initial conditions $b_{-3}=b_{-2}=b_{-1}=0$ and $b_0=1$. This is the sequence https://oeis.org/A123392.

For the $1\times 10$ problem, we obtain $b_8=461$, $b_9=1068$, $b_{10}=2474$, and hence $r_{10}=1529$. The sum $b_{10}+r_{10}$ is the number we are looking for.

Remark. If we want to obtain the number of tilings after the identification by reflection in the "vertical" mediator of the $1\times 10$ rectangle, the study of the tilings of the $1\times 5$ rectangle is needed and some considerations about the action of the group $\{-1,1\}$ (of the reflection) on the tilings of the $1\times 10$ rectangle.