Tiling a $3 \times 2n$ rectangle with dominoes

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?

Solution 1:

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.

Solution 2:

For a given tiling of $3 \times 2n$, let's see if we can break it up into a $ 3 \times k$ and $ 3 \times (2n-k) $ rectangle with a clean vertical break.
Specifically, consider the smallest $k\geq 1 $ such that there is no domino that is in both columns $k$ and $k+1$. A simple parity check shows that $k$ must be even.

For $k=2$, there are 3 ways to tile the initial portion - all horizontal, only top horizontal, only bottom horizontal.

For $k\geq 4$, there are 2 ways to tile the initial portion - only top horizontal, only bottom horizontal.

Thus, this gives us that $f(n) = 3 f(n-1) + 2f(n-2) + 2 f(n-3) + \ldots + 2 f(0)$.

Similarly, $f(n-1) = 3f(n-2) + 2f(n-3) + \ldots + 2f(0)$.

Hence $f(n) - f(n-1) = 3f(n-1) - f(n-2)$, which gives

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