Domino tiling

A domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

Domino tiling of a square

[edit] Height functions

For some classes of tilings on a regular grid in two dimensions, it is possible to define a height function associating an integer to the nodes of the grid. For instance, draw a chessboard, fix a node A₀ with height 0, then for any node there is a path from A₀ to it. On this path define the height of each node A_{n + 1} (i.e. corners of the squares) to be the height of the previous node A_nplus one if the square on the right of the path from A_n to A_{n + 1} is black, and minus one else.

More details can be found in Kenyon & Okounkov (2005).

[edit] Thurston's height condition

William Thurston (1990) describes a simple test for determining whether a simply-connected region, formed as the union of unit squares in the plane, has a domino tiling. He forms an undirected graph that has as its vertices the points (x,y,z) in the three-dimensional integer lattice, where each such point is connected to four neighbors: if x+y is even, then (x,y,z) is connected to (x+1,y,z+1), (x-1,y,z+1), (x,y+1,z-1), and (x,y-1,z-1), while if x+y is odd, then (x,y,z) is connected to (x+1,y,z-1), (x-1,y,z-1), (x,y+1,z+1), and (x,y-1,z+1). The boundary of the region, viewed as a sequence of integer points in the (x,y) plane, lifts uniquely (once a starting height is chosen) to a path in this three-dimensional graph, and the region can be tiled if and only if this path closes up to form a simple closed curve in three dimensions.

Domino tiling of an 8×8 square using the minimum number of long-edge-to-long-edge pairs (1 pair in the center).

[edit] Counting tilings of squares

The number of ways to cover a 2n-by-2n square with 2n² dominoes (as calculated independently by Temperley and M.E. Fisher and Kasteleyn in 1961) is given by

The sequence of values generated by this formula for 2n = 0, 2, 4, 6, 8, 10, 12, ... :

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sequence A004003 in OEIS).

The calculation of the number of possible ways of tiling a standard chessboard with 32 dominoes is a simple, commonly used, example of a problem which may be solved through the use of the Pfaffian technique. This technique may be applied in many mathematics-related subjects, for example, in the classical, 2-dimensional computation of the dimer-dimer correlator function in quantum mechanics.

[edit] See also

• Statistical mechanics
• Mutilated chessboard problem, a puzzle concerning domino tiling of a 62-square subset of the chessboard
• Tatami, floor mats in the shape of a domino that are used to tile the floors of Japanese rooms, with certain rules about how they may be placed

[edit] References

• Bodini, Olivier & Latapy, Matthieu (2003), "Generalized Tilings with Height Functions", Morfismos 7(1): 47–68, ISSN 1870-6525, <http://www-rp.lip6.fr/%7Elatapy/Publis/morfismos03.pdf> .
• Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice", Physica 27(12): 1209–1225, doi:10.1016/0031-8914(61)90063-5 .
• Kenyon, Richard & Okounkov, Andrei (2005), "What is … a dimer?", Notices of the American Mathematical Society 52(3): 342–343, ISSN 0002-9920, <http://www.ams.org/notices/200503/what-is.pdf> .
• Propp, James (2005), "Lambda-determinants and domino-tilings", Advances in Applied Mathematics 34(4): 871–879, doi:10.1016/j.aam.2004.06.005, arΧiv:math.CO/0406301 .
• Sellers, James A. (2002), "Domino tilings and products of Fibonacci and Pell numbers", Journal of Integer Sequences 5(Article 02.1.2), <http://www.emis.de/journals/JIS/VOL5/Sellers/sellers4.pdf> .
• Thurston, W. P. (1990), "Conway's tiling groups", American Mathematical Monthly 97(8): 757–773, doi:10.2307/2324578 .
• Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (revised ed.), p. 182, ISBN 0-14-026149-4 .