Return to Revisions

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height $2$ are used, then we reduce to the $1 \times n$, so there are $2^{2n-2}$ ways to do this. Otherwise, we condition on the rightmost rectangle of height $2$. This yields, $$ T(n)=2^{2n-2}+\sum_{k=0}^{n-1} T(k)+\sum_{0\leq k < \ell \leq n-1}T(k)2^{2(n-\ell-1)}, $$ with the initial conditions $T(0)=1$ and $T(1)=2$.