15
$\begingroup$

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?

2 Answers 2