# Calculate the number of tiling combinations

Source - Zonal Informatics Olympiad 2006 Question Paper

Have tried deriving the answer through solutions to smaller problems, but of no avail.

-
Try coming up with two recurrence relations, one for a flat edge and one for a bumpy edge. – wj32 Nov 1 '12 at 8:00

If $f(n)$ is the number of ways of tiling a $2 \times n$ rectangle then $$f(n)=f(n-1)+f(n-2)+2\sum_{j\lt n-2}f(j)$$ starting at $f(0)=1$, since the right hand end can be a vertical double tile, two horizontal double tiles, or in two orientations an L on the end with repeating horizontal doubles eventually capped by another L.
You can now answer the particular questions by hand, or by noting this is also $$f(n)=2f(n-1)+f(n-3)$$ starting at $f(0)=f(1)=1$, with the generating function $1/(1-2x-x^3),$ or just look up OEIS A052980 .
Not quite true, how about an $L$ on the end with repeating horizontal doubles eventually capped by another $L$. – EuYu Nov 1 '12 at 8:02
@7Aces: the first function comes for removing the first height 2 rectangle at the right, the second by looking at $f(n)-f(n-1)$. – Henry Nov 1 '12 at 13:26