God Plays Dice: tilings

Showing posts with label tilings. Show all posts

17 February 2009

Pavages aléatoires par touillage de dominos

Pavages aléatoires par touillage de dominos, by Thierry de la Rue et Elise Janvresse. ("Random tilings by domino shuffling", roughly.) This expository article describes work, mostly by Jim Propp and coauthors, on the generation of random tilings. As you can guess from the title, it's in French. If you don't read French you can look at the pretty pictures.

Also, this article is on a web page; the people who make the web page have used Javascript in such a way that in various places, if you want more detail, there's a link that you can click on and more detailed explanations will appear in place in the article. This may be a useful presentation technique, although it's hard to know because this is the first time I've seen it.

08 September 2008

Doubly mutilated chessboard problem: not the solution

On Friday I wrote about the mutilated chessboard problem.

I'll give the solution now. The reason this problem is usually phrased in terms of a "chessboard" is that a chessboard has its squares alternately colored white and black. (I'm going to call the colors white and black even if that's not actually what they are.) A chessboard has the same number of squares of each color, and any domino covers one white square and one black square. So if we remove two squares of the same color, such as the opposite corners, then tiling is impossible.

It turns out that if you remove any two squares of different color, leaving 31 squares of each color, the board can be tiled with dominoes. Drini gave the solution; draw any tour that goes through all the squares exactly once and finishes where it began. Removing two squares of opposite colors breaks this into two subpaths of even length, which are easily tiled.

As for the other problem I asked, when can you remove four squared and have there be a tiling: clearly we need to begin by removing two squares of each color. There is another necessary condition for there to be a tiling -- the squares removed can't block off a single corner square from the rest of the board. (You might worry that they could disconnect the board in some other way, but the only other way possible under the tiling constraints is that they disconnect a domino-shaped region.) But then the tour argument above doesn't work; in particular, a tour is broken up into four subpaths of even lengths if and only if the removed squares occur on it in the order black-white-black-white. Furthermore, it appears that there are ways to remove four squares from the four-by-four board such that the remaining twelve are tileable, but there is no tour that they break up into even-length subpaths. There aren't that many tours of the four-by-four board, so it's easy to check this by brute force with a simple program; in fact there are six according to Sloane's encyclopedia. (It says twelve there, but Sloane refers to directed tours.)

However, that cuts down the number of cases one has to deal with, and in the end it looks like a four-by-four chessboard, with four squares removed, is tileable if and only if the removed squares are of opposite color and do not include both of the squares adjacent to any corner.

My method (which I realize I haven't fully explained here; if anybody wants to seriously tackle this problem for some reason I'll be happy to explain in more detail) requires a bunch of nasty case analysis, though. And in the case of the 8-by-8 board there are millions of tours, so it doesn't generalize well.

05 September 2008

Best Wikipedia article title ever

Mutilated chessboard problem.

The problem is the folkloric one: given a chessboard with two diagonally opposite corners removed, can you tile it with dominoes? A domino is a rectangle which is the size of two adjacent squares. (If you haven't seen it, think about it; the solution is in the article.)

I've known this problem for as long as I can remember, but I didn't realize it had a name. I didn't realize it needed a name. But apparently it's a standard example of a theorem which is hard for automated theorem-proving programs, so that community needed something to call it, because they can't refer to "that one with the dominoes on the chessboard where you get rid of two squares" in the title of their papers.

Harder question, again if you haven't seen it before: when can you remove two squares and have there be a tiling? (I know the answer. If you want to know it, leave a comment.)

Even harder question: when can you remove four squares and have there be a tiling? This might not be that difficult, but I don't know the answer. (It'll give me something to think about on the walk into school this morning, though.)

15 December 2007

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