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. 

 A: 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.
A: 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.  
A: 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$)
A: 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}$. 
