Finding the reccurence relation from a problem.

Question

let $f(n)$ be the number if ways to lay down tiles in a formation of size 2 x n using tiles of size: $$ \begin{matrix} 1 \\ 1 \\ \end{matrix} $$ and tiles of size: $$ \begin{matrix} 1 & 1 & 1 \\ 1 & \\ \end{matrix} $$

Turning and reflecting the tiles is legal.

So what i thought was that theres 2 illegal starts:

$$ \begin{matrix} 1 & 1 & 1 \\ & & 1 \\ \end{matrix} $$

and : \begin{matrix} & & 1 \\ 1 & 1 & 1 \\ \end{matrix}

And so there's the options to set the 2X1 tile vertically and the $f_{n-1}$ and all the rest of the cases (6 more) i set the first two so it fills the formation legally and then $f_{n-2}$,

So suming up all: $f_n=f_{n-1}+6f_{n-2}$

$f_0=0 , f_1=1$

but it is not working... help would be appreciated. thanks.

Answer 1

There are $8$ different ways the left most tiles of a $2\times n$ tiling could look.

• It could have a vertical $2\times 1$ tile. This only takes up 1 horizontal slot. This gives us a summand of $f_{n-1}$ in the reccurence.

• It could have $2$ horizontal $2\times 1$ tiles. This formation takes up 2 horizontal slots. This gives us a summand of $f_{n-2}$.

• It could start with an L shaped tile and a horizontal $2\times 1$ tile in 4 different ways (crudely pictured below). All of these take up $3$ horizontal slots. This gives us a summand of $4f_{n-3}$.

  • $$\begin{matrix} a & a & b \\ b& b & b\end{matrix}$$
  • $$\begin{matrix} b & a & a \\ b& b & b\end{matrix}$$
  • $$\begin{matrix} b & b & b \\ a& a & b\end{matrix}$$
  • $$\begin{matrix} b & b & b \\ b& a & a\end{matrix}$$

• It could start with 2 interlocking L shaped tiles in 2 different ways. These formations take up $4$ horizontal slots. This gives us a summand of $2f_{n-4}$.

  • $$\begin{matrix} a & a & a & b \\ a & b & b & b\end{matrix}$$
  • $$\begin{matrix} b & a & a & a \\ b & b & b & a\end{matrix}$$

So the total recurrence relation is given by $f_n=f_{n-1}+f_{n-2}+4f_{n-3}+2f_{n-4}$ with starting conditions $f_0 = 1$, $f_1=1$, $f_2=2$ and $f_3=7$.

Note that $f_0 =1$ and not $0$ since there is exactly one way to tile a $2\times 0$ strip, it uses $0$ tiles.