Return to Question

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 $10$.

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$.

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.

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 $10$.