# Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?

I've done some work on this and have found a way of calculating this that's polynomial time in $n$ by reducing it to counting the number of paths from a source to sink in a DAG with $\mathcal O(n^2)$ vertices and $\mathcal O(n^3)$ edges. I'm pretty sure this doesn't overcount, which is easy to do if you're not careful. Problem is it's not pretty.

I'm looking for either a simple closed form, generating function, recursion, fast algorithm...

For $1 \times n$ rectangles, there are $2^{n-1}$ ways to do this. In the $2 \times n$ case, the problem seems much harder.

A reference to literature would be greatly appreciated.

Apologies if this question is not appropriate for this site.

For $n=1$, you should get $2$. For $n=2$, you should get $8$.

Let $f(m,n)$ be the number of ways to tile a shape consisting of a $1 \times m$ rectangle on top of a $1 \times n$ rectangle with right sides aligned. You want $f(n,n)$. If $m \ne n$, the leftmost tile could be a $1 \times j$ for $1 \le j \le \max(m,n)$. If $m = n$, you could have a $2 \times j$ or a $1 \times j$ atop a $1 \times k$. Thus
$$f(m,n) = \cases{\sum_{j=1}^m f(m-j,n) & if m > n\cr \sum_{j=1}^n f(m,n-j) & if m < n\cr \sum_{j=1}^m f(m-j,m-j) + \sum_{j=1}^m \sum_{k=1}^m f(m-j,m-k) & if m = n\cr}$$ $f(n,n)$ is OEIS sequence A034999.
• Sorry, mistake in my program, corrected. Actually you want $f(2,2)=8$. – Robert Israel Feb 2 '16 at 16:47
• At OEIS, it says $a_n=6a_{n-1}-7a_{n-2}$. I wonder how one gets that? – Gerry Myerson Feb 2 '16 at 21:53
• i.e. multiply Tony's equation by $x^n$, sum for $n=1 \ldots \infty$ (interchanging the order of summations) and add $1$, and you should get $$g(x) = \dfrac{x}{1-4x} + \dfrac{x g(x)}{1-x} + \dfrac{x^2 g(x)}{1-5x+4x^2}$$ where $g(x)$ is the g.f. Solve: $$g(x) = \dfrac{1-4x+3x^2}{1-6x+7x^2}$$ – Robert Israel Feb 3 '16 at 1:25
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 two independent instances of the $1 \times n$ case, and 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$. Note that the formula $2^{n-1}$ for the $1 \times n$ case is not correct if $n=0$, so the middle term in the recursion corresponds to the case that the rightmost rectangle of height $2$ is actually the rightmost rectangle in the tiling.