2
$\begingroup$

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.

[edit]

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

$\endgroup$
8
$\begingroup$

(EDITED)

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.

$\endgroup$
  • $\begingroup$ Sorry, mistake in my program, corrected. Actually you want $f(2,2)=8$. $\endgroup$ – Robert Israel Feb 2 '16 at 16:47
  • $\begingroup$ At OEIS, it says $a_n=6a_{n-1}-7a_{n-2}$. I wonder how one gets that? $\endgroup$ – Gerry Myerson Feb 2 '16 at 21:53
  • 2
    $\begingroup$ You should be able to get the g.f. from Tony Huynh's recursion equation, and it follows from that. $\endgroup$ – Robert Israel Feb 2 '16 at 22:17
  • 2
    $\begingroup$ 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}$$ $\endgroup$ – Robert Israel Feb 3 '16 at 1:25
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.