God Plays Dice: Tilings of the plane

For various reasons, I've been thinking about tilings of the plane a lot lately. This reminded me of a paper I haven't thought about in a while, by Cris Moore, Some Polyomino Tilings of the Plane, which "calculates generating functions for the number of tilings of rectangles of various widths by" various polyominoes. Let T_m,n be the number of tilings of an m-by-n board by a given set of tiles; then the bivariate generating function

$\sum_{m \ge 0} \sum_{n \ge 0} T_{m,n} x^m y^n$

is in general a quite complicated object. (I don't know of any explicit examples of this function, which I think just goes to show that it's complicated!) Even the "diagonal" generating function,

$\sum_{n \ge 0} T_{n,n} x^n$

which has as the coefficient of xⁿ the number of tilings of an n-by-n square, seems to be on the ugly side. On the contrary,

$\sum_{n \ge 0} T_{m,n} x^n$

is usually a rational function. In a sense tilings of strips of fixed width are a "one-dimensional" problem -- for example, one could encode tilings of fixed-width strips with a certain set of tiles as words over some finite alphabet, I suspect. The fact that these generating functions are rational seems to be a "folk theorem" -- anybody who's thought about tilings knows it, but I've never seen a proof.

For example, the number of tilings of the 2-by-n rectangle with dominoes are just the Fibonacci numbers! (See Mathworld's pictures.) This is easy to see. Let T_n be the number of ways to tile a 2-by-n rectangle with domnioes. The left edge of a 2-by-n rectangle (that's 2 rows, n columns) tiled with dominoes is either a single vertical domino, in which case there are T_n-1 ways to finish the tiling, or two horizontal ones, in which case there are T_n-2 ways to finish the tiling. So T_n = T_n-1 + T_n-2; noting that T₁ = 1, T₂ = 2 finishes the proof.

But the number of tilings of an m-by-n rectangle by dominoes is given by the quite difficult formula

$T_{m,n} = 2^{mn/2} \prod_{j=1}^m \prod_{k=1}^n \left( \cos^2 {j\pi \over m+1} + \cos^2 {k\pi \over n+1} \right)^{1/4}$

which is one of those curious formulas that occur in combinatorics in which some expression that has no business even being an integer is not only an integer, but manages to count something! (Notice that if both m and n are odd, then the number of domino tilings of T_m,n should be zero; the formula takes care of this nicely. Namely, if m and n are both odd then the j = (m+1)/2, k = (n+1)/2 term of the product is zero. (I'm quoting Graham, Knuth, and Patashnik for this formula; it's originally due to Kasteleyn. Anybody who mentions domino tilings is required by law to cite Kasteleyn's paper.) There's a rather strange interpretation of this formula I read somewhere once: given an m-by-n board, you can write the number

$2^{1/2} \left( \cos^2 {j\pi \over m+1} + \cos^2 {k\pi \over n+1} \right)^{1/4}$

in the (j, k) square, and the product of those numbers is the number of domino tilings of the board.

Furthermore, if you consider log T_m,n the product becomes a sum:

$\log T_{m,n} = {mn \over 2} \log 2 + {1 \over 4} \sum_{j=1}^m \sum_{k=1}^n \log \left( \cos^2 {j\pi \over m+1} + \cos^2 {k\pi \over n+1} \right)$

and we can approximate that sum by an integral, since it's a Riemann sum; thus

$\log T_{m,n} \approx {mn \over 2} \log 2 + {mn \over 4\pi^2} \int_0^\pi \int_0^\pi \log(\cos^2 x + \cos^2 y) \thinspace dx \thinspace dy .$

The integral isn't elementary, but it can be evaluated numerically; thus we get log T_m,n ≈ .29156 mn.

Perhaps a bit surprisingly, this only depends on the size of the rectangle being tiled, not its shape; that's not quite true, though, because the approximation by an integral is a bit crude. Still, for example, an 80 by 80 rectangle has 1.18 × 10⁸⁰⁰ domino tilings, while a 40 by 160 rectangle has 4.26 × 10⁷⁹⁷; in terms of the logarithm (which is how these things should be viewed) those are quite close. There are deep connections to statistical physics here that I don't quite understand, although I could if I put my mind to it; the limit of log T_m,n/mn as m and n get large is called the entropy of a set of tiles (Moore), and I believe something like this is true for any set of tiles, although entropies aren't exactly easy to calculate.

References
1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik. Concrete Mathematics, 2nd edition. Addison-Wesley, 1994.
2. P. W. Kasteleyn, "The statistics of dimers on a lattice, I: The number of dimer arrangements on a quadratic lattice." Physica 27 (1961) 1209-1225.
3. Cris Moore, "Some Polyomino Tilings of the Plane". Availalable from author's web site, http://www.santafe.edu/~moore/.

God Plays Dice

15 December 2007

Tilings of the plane

No comments:

Blog Archive

Contributors

Other blogs