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

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.
• What have you tried so far? – Vinyl_cape_jawa Feb 23 at 15:05
• I couldn't come to any solution – Abhinav Feb 23 at 15:08
• I don't know how to start – Abhinav Feb 23 at 15:08
• Maybe you can try doing this recursively, like A[12]=A[11]+A[9], and I think you need a B to tell about if one block is stuck out, like this(can anyone tell me how to change the line please) – Math Lover Feb 23 at 15:09
• The area you need to tile is not big at all, try out some – Vinyl_cape_jawa Feb 23 at 15:09

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.

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.

• I have another idea. Can we make groups of 2*2 boxes with 2 I-shaped tiles. By P&C we can make that total number of combinations would be $2^6$.Similarly for 3*2 box and so on. After we complete upto 6*2 box we can add the earlier combinations. – Abhinav Feb 23 at 16:12

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$$)

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}$$.