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?
Best 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.