On Rectangular Tilings

Rather than trying to solve the problem in general, let's look at some specific values of m.

The 1 × n case isn't interesting at all. If n is even, there's exactly one way to tile the board, while if n is odd, there are none.

The 2 × n case is better. Suppose we work from left to right, filling in a column at a time. In the first column, we can place either a single vertical tile or a pair of horizontal tiles, like so.

Then, since the first column is complete, we can shift our attention to the next column, which will be either empty or already full.

In other words, in a single step of filling and shifting, there's one way to get from an empty column back to an empty column, and one way to get from an empty column to a full column.

What happens to a full column in a single step? Well, there's nothing to fill, so all we have to do is shift, producing an empty column. In other words, there's one way to get from a full column to an empty column, and nothing else.

If we represent empty and full columns by the (column) vectors e₁ = (1 0) and e₂ = (0 1), then the transformation that occurs in a single step is nicely represented by the 2 × 2 matrix M shown below.

1	1
1	0

If we compute, say, the eighth power of the matrix,

34	21
21	13,

and multiply by the vector (1 0) representing an empty column, we can see that in eight steps of filling and shifting, there are 34 ways of getting from an empty column back to an empty column, and 21 ways of getting from an empty column to a full column. But, if we've gone from an empty column to an empty column in eight steps, we've just tiled a 2 × 8 rectangle!

In general, then, the number of ways of tiling a 2 × n rectangle is given by the upper left corner of the matrix Mⁿ, i.e.,

ways(2,n) = e₁^† Mⁿ e₁.

You might have noticed that the numbers 13, 21, and 34 are all Fibonacci numbers. That's no accident, and in fact it's not hard to show that ways(2,n) = F(n+1), but I'm going to skip that and look at something I find more interesting. Suppose we expand the matrix M in terms of its eigenvalues a_i and normalized eigenvectors v_i.

M = sum ( a_i v_i v_i^† )

(It so happens that the eigenvectors are orthogonal, otherwise the formula would be a little different.)

The n^th power of M is then

Mⁿ = sum ( a_iⁿ v_i v_i^† ),

and the number of ways of tiling a 2 × n rectangle is

ways(2,n) = sum ( a_iⁿ | e₁^†v_i |² ).

Finally, substituting in the actual eigenvalues and eigenvectors, we obtain

ways(2,n) = (1/R) [ ((1+R)/2)ⁿ⁺¹ − ((1−R)/2)ⁿ⁺¹ ],

where R is the square root of 5. The factor (1+R)/2 is the golden mean, by the way, and the right hand side is a well-known formula for the (n+1)^st Fibonacci number.

For large values of n, we can get a good approximation to the right answer by ignoring all but the largest eigenvalue.

ways(2,n) ~ ((1+R)/2)ⁿ⁺¹ / R

Now, here's a neat thing. The exact same technique, of looking at the largest eigenvalue of a transfer matrix, can be used in physics to compute the thermodynamic properties of certain types of material! How about that? If you're curious as to details, I don't have a reference handy, but the example I have in mind is the one-dimensional Ising model.

Now let's look briefly at the 3 × n case. To write down the transfer matrix, it will help to have a list of all the possible states a column can be in. Since each of the three squares can be either empty or full, the states correspond to three-digit binary numbers, like so.

Actually, it's better to put the states in a different order, such as the following,

because then the transfer matrix becomes block diagonal.

0	1	1	0	1	0
1	0	0	0	0	0
1	0	0	1	0	0
0	0	1	0	0	0
1	0	0	0	0	1
0	0	0	0	1	0
						0	1
						1	0

Substituting the actual eigenvalues and eigenvectors into the formula above, and being careful to take into account that there are two equally large eigenvalues, we obtain the following result for even values of n.

ways(3,n) ~ ((1 + root 3)/(root 2))ⁿ⁺¹ / (root 6)

For odd values of n, of course, the number of squares on the board is odd, so no tilings are possible.

I'm not sure why I like this technique so much. If you happen to like it too, and want more variants to play with, you might try allowing 1 × 1 tiles as well, or using other tile shapes, or perhaps applying periodic boundary conditions in one direction or another.

Unfortunately, the technique as I've presented it is not much use for the general m × n case. However, the general case does have a solution—the standard reference is an article by Kasteleyn. I wasn't able to find a copy on line, but I did manage to find a few other interesting pages, like this one.