1
$\begingroup$

Problem Statement Problem Statement

Source - Zonal Informatics Olympiad 2006 Question Paper

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

  • 1
    Try coming up with two recurrence relations, one for a flat edge and one for a bumpy edge.2012-11-01

1 Answers 1

3

Now incorporating EuYu's comment:

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 .

  • 0
    @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)$.2012-11-01