Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2 Answers 2

For a given tiling of $3 \times 2n$, consider the smallest $k\geq 1 $ such that there is no domino that is in both $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)$$

share|improve this 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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