Number of ways the room can be tiled with $I$ shaped and $L$ shaped tiles

Question

There is a room of dimension $2\times 12$ units. You have to tile it. There are two types of tiles:

• I-Shaped - it is of a dimension $1\times 2$ units,
• L-Shaped - it is in the shape of $L$ which has an area of $3$ sq. units.

In how many ways can you tile it?

I have studied some basics of permutation and combination but I can't use it in the this question.

Note:

• The $I$ shaped tiles are identical from both sides.
• You can rotate the tiles in any direction if it will fit.
• You have an unlimited supply of tiles.

Answer 1

I am not quite sure if you can use basic permutation/combination to solve this problem.

But It can be approached recursively.

Denote the number of ways of tiling a $2\times n$ area by given tiles as $T(n)$, and the number of ways of tiling a $2 \times n$ area plus a leading block on top or bottom as $S(n)$

Then,

$T(n)=T(n-1)+T(n-2)+ 2S(n-2)$

$S(n)=S(n-1)+T(n-1)$

Take the first relation for example. If you lay the first tile as 'I' and vertically, you result in a $2\times (n-1)$ area. If you lay the first tile 'I' horizontally, you will have to cover the area below it with another horizontal 'I' to cover fully, you get a $2\times (n-2)$ area. If you lay a 'L', you can do it in two valid way, and by symmetry, they have same number ways of being tiled, names $S(n-2)$.

By solving the recurrence relation, you can get the answer to $T(12)$, i.e., your question.

Answer 2

HINTS:

Since the are you need to tile is not that big at all you could easily just list all the tilings (which is definitely not a pretty way to solve it but if you have no idea how to start it at least gives you a starting point).

Using an odd number of $L$ shaped tile you won´t succeed so you can directly start checking the cases where you have an even number of $L$ tiles.

Using $0$ of the $L$ tiles you will be able to tile it using only the $I$ shaped ones and this can be done in only $1$ way.

Using $2$ of the $L$ shaped ones you have $4$ cases,

1) they are next to each other

2) they have $2$ of the $I$ shaped ones inbetween them

3) they have $4$ of the $I$ shaped ones inbetween them

4) they have $6$ of the $I$ shaped ones inbetween them

Observe that in each of these cases you get a factor of $2$ in the number of solutions since each of these can be flipped around a horisontal axis.

And so on...

As I said this is definitely not a nice solution, creating a recurrence relation is a lot nicer altough I am unsure if you know how to use recurrence relation to solve this. Please let me know if you do, in that case we could work out something more mathematical :)

Hope this helped.

Answer 3

Let $A_n,B_n,C_n,D_n$ denote the following four shapes, where $n$ is the width of the shape. Let $a_n,b_n,c_n,d_n$ be the number of ways to tile them, respectively.

The top right field of $A_n$ can be covered by a vertical $I$, by a horizontal $I$, by the apex of an $L$, or by the "toe" of an $L$. Removing this tile produces either the shape $A_{n-1}$, $D_n$, $B_{n-1}$, or $C_{n-1}$, respectively. We conclude $$\tag1a_n=a_{n-1}+d_n+b_{n-1}+c_{n-1}.$$ The rightmost field of $B_n$ can be covered by a horizontal $I$ or by the "toe" of an $L$. Removing this tile produces either $C_{n-1}$ or $A_{n-2}$, respectively. We conclude $$\tag2b_n=c_{n-1}+a_{n-2}.$$ The rightmost field of $D_n$ can only be covered by a horizontal $I$. We conclude $$\tag3d_n=a_{n-2}.$$ And by symmetry, we clearly have $$ \tag4c_n=b_n.$$ Using $(3)$ and $(4)$ to eliminate $c_n$ and $d_n$, we find $$ a_n=a_{n-1}+a_{n-2}+2b_{n-1}$$ and $$a_{n+1}=a_n+a_{n-1}+2b_n=a_n+a_{n-1}+2(b_{n-1}+a_{n-2})$$ and from these eliminate $b_{n-1}$: $$a_{n+1}= 2a_n+a_{n-2}.$$ This recursion is good enough to quickly compute the desired value $a_{12}$ by hand from the readily obtained starting values $$a_0=1, \quad a_1=1, \quad a_2=2.$$ (The recursion can also be used to ultimately obtain an explicit formula for $a_n$ for arbitrary $n$)

Answer 4

Here is a combinatorial proof of the following recurrence mentioned at the end of Hagen von Eitzen's answer. $$ a_n=2a_{n-1}+a_{n-3} $$ To specify a tiling of a $2\times n$ rectangle, start with a tiling of a $2\times (n-1)$ board, add a vertical $I$ tile to the left end, then do one of two things:

• Leave it as is.

• Make whichever of the below replacements is possible, where the xs mark the $I$ tile at the left end.

X Y    ->  X X
X Y        Y Y

X L L  -> L X X
X L       L L

X L    -> L L
X L L     L X X

X Y Y  -> L M M
X Z Z     L L M

This generates almost all possible $2\times n$ tilings. The only ones remaining are the ones ending in

L L M
L M M,

which are accounted for by the $a_{n-3}$.