Take the tour ×

I'm looking to find out if there's any easy way to calculate the number of ways to tile a $3 \times 2n$ rectangle with dominoes. I was able to do it with the two codependent recurrences

f(0) = g(0) = 1
f(n) = f(n-1) + 2g(n-1)
g(n) = f(n) + g(n-1)

where $f(n)$ is the actual answer and $g(n)$ is a helper function that represents the number of ways to tile a $3 \times 2n$ rectangle with two extra squares on the end (the same as a $3 \times 2n+1$ rectangle missing one square).

By combining these and doing some algebra, I was able to reduce this to

f(n) = 4f(n-1) - f(n-2)

which shows up as sequence A001835, confirming that this is the correct recurrence.

The number of ways to tile a $2 \times n$ rectangle is the Fibonacci numbers because every rectangle ends with either a verticle domino or two horizontal ones, which gives the exact recurrence that Fibonacci numbers do. My question is, is there a similar simple explanation for this recurrence for tiling a $3 \times 2n$ rectangle?

share|improve this question
add comment

1 Answer

Here's my best shot at the sort of explanation you're asking for, although it's not nearly as clear as the $2 \times n$ case. The negative sign makes combinatorial proofs difficult, so let's rearrange this as:

$$f(n) + f(n-2) = 4f(n-1)$$

Then you want to show that the number of $n$-tilings, plus the number of $(n-2)$-tilings, is four times the number of $(n-1)$-tilings. (An "n-tiling" is a tiling of a $3 \times 2n$ rectangle by dominoes.)

In bijective terms, then, we want a bijection between the set of $n$-tilings and $(n-2)$-tilings and the set of $(n-1)$-tilings, where the $(n-1)$-tilings are each tagged with the number $1, 2, 3,$ or $4$.

Given an $(n-1)$-tiling, there are three "obvious" ways to obtain an $n$-tiling from it, namely by adding one of the three $1$-tilings on the right end. These generate tilings which have a vertical line passing all the way through, two units from the right end; call these "faulted" tilings, and those which don't have a vertical line in that position "faultless".

So it suffices to show that the number of faultless $n$-tilings, plus the number of $(n-2)$-tilings, is the number of $(n-1)$-tilings. It's easy to see that the number of faultless $n$-tilings is $2g(n-2)$; a faultless tilings must have a horizontal domino covering the second and third squares from the right in some row, and this assumption forces the placement of some other dominoes. So we need $2g(n-2) + f(n-2) = f(n-1)$. Shifting the indices, we need $2g(n-1) + f(n-1) = f(n)$, which you have already said is true.

share|improve this answer
add comment

Your Answer


