Cover a wall $2\times7$ with $1\times1$ tile and $2\times 1$ tile

Question

A wall with dimensions $2\times7$ squares has to be covered with ceramic tiles. There are two tiles of ceramic tiles that are available: the $1\times1$ (identical) tile and the $2\times1$ (identical) tile. The $2\times1$ tile can be rotated before being placed on the board. We are provided with as many tiles of each type as we need. In how many ways can we cover the $2\times7$ wall with such tiles?

My idea: consider the cases: have no $2\times1$ tile, have one $2\times1$ tile, have two $2\times1$ tiles, have three $2\times1$ tiles, and so on up to seven $2\times1$ tiles, but that is too complicated and I don't know how to do. Please everyone help me.

Answer 1

I will make frequent use of the words "domino" and "monomino" in this problem.

Let $a_k$ represent the number of ways to tile a $2\times k$ wall. We will seek to find a recurrence relation for $a_{k+1}$ by considering the rightmost between-column where there is a vertical line that doesn't cut through a domino.

Here will be the different summands of $a_{k+1}$:

• $2a_k$: There are two different ways to "cleanly" cover just the last column: one domino or two monominoes.
• $3a_{k-1}$: There are three different ways to cleanly cover exactly the last two columns: two dominoes one above the other, a domino on top and two monominoes on bottom, and a domino on bottom and two monominoes on top.
• $2a_{k-2}$: There are two ways to cleanly cover exactly exactly the last three columns:
• $2a_{k-3}+2a_{k-4}+\cdots+2a_1$+: Extending the same zipper pattern further, there are exactly two ways to cover any extra number of columns.

So we have $$a_{k+1}=2a_k+3a_{k-1}+2a_{k-2}+...+a_1,\ a_0=1$$

This is A030186 in OEIS. Also note that, since $$a_k=2a_{k-1}+3a_{k-2}+2a_{k-3}+...+a_1$$ we can rearrange and add the two equations together to get

$$a_{k+1} = 3a_k + a_{k-1} - a_{k-2}$$ Either way, $a=(1,2,7,22,71,228,733,2356,\cdots)$, so $a_7=2356$.

Answer 2

Let $W_n:=[0,n]\times[0,2]$ be the wall. Denote by $a_0(n)$ the number of perfect tilings of $W_n$, by $a_1(n)$ the number of tilings of $W_n$ with a single overlapping square, coming from a $2\times1$ block, at the upper right. Then $a_1(n)$ is also the number of tilings of $W_n$ with a single overlapping square at the lower right. Finally let $a_2(n)$ be the number of tilings of $W_n$ with two overlapping squares at the right, coming from two $2\times1$ blocks. Collect the $a_i(n)$ into the column vector $$a(n):=[a_0(n), \ a_1(n), \ a_2(n)]'\ .$$ One has $a(0)=[1, \ 0,\ 0]'$. Inspecting figures one sees that the $a_i(n)$ satisfy the following recursion: $$\eqalign{a_0(n)&=2a_0(n-1)+2a_1(n-1)+a_2(n-1)\cr a_1(n)&=a_0(n-1)+a_1(n-1)\cr a_2(n)&=a_0(n-1)\ .\cr}\tag{1}$$ This means that $$a(n)=M a(n-1)\qquad(n\geq1)$$ with the matrix $$M=\left[\matrix{2&2&1\cr1&1&0\cr 1&0&0\cr}\right]\ .$$ For your wall we have to compute $a(7)=M^7 a(0)$. Mathematica did this for me and obtained $a_0(7)=2356$.

Playing around with $(1)$ one finds that the numbers $x_n:=a_0(n)$ satisfy the recursion $$x_0=1,\quad x_1=2,\quad x_2=7,\qquad x_n=3x_{n-1}+x_{n-2}-x_{n-3}\quad(n\geq3)\ .$$