> urticator.net

  About This Site
> Domains

> Math

  Game Theory Section
  A Theorem on Finite Abelian Groups
> Miscellaneous

  Commutative Diagrams
> On Rectangular Tilings
  The Euclidean Algorithm
  Continued Fractions
  The Twelve-Note Scale
  Tesseract Model
  The Pentagon Knot

On Rectangular Tilings

Suppose we have a m × n checkerboard and want to know how many different ways we can tile it, that is, cover it with 2 × 1 tiles. For example, here are two ways of tiling a 4 × 4 board.

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 e1 = (1 0) and e2 = (0 1), then the transformation that occurs in a single step is nicely represented by the 2 × 2 matrix M shown below.


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


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 Mn, i.e.,

ways(2,n) = e1 Mn e1.

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 ai and normalized eigenvectors vi.

M = sum ( ai vi vi )

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

The nth power of M is then

Mn = sum ( ain vi vi ),

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

ways(2,n) = sum ( ain | e1vi |2 ).

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

ways(2,n) = (1/R) [ ((1+R)/2)n+1 - ((1-R)/2)n+1 ],

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)n+1 / 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.


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))n+1 / (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.


  See Also

@ March (2001)