Domino tiling

A domino tiling of a region in the Euclidean plane is a tesselation 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.

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.

Counting tilings of squares

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

$\prod _{j=1}^{N}\prod _{k=1}^{N}\left(4\cos ^{2}{\frac {\pi j}{2n+1}}+4\cos ^{2}{\frac {\pi k}{2n+1}}\right)$

The sequence of values generated by this formula is

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sequence A004003 in the 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.

See also

• Pfaffian
• Dimer
• Polyomino
• Statistical mechanics
• Dominoes on a chessboard puzzle

References

• The statistics of dimers on a lattice, Part I, Physica, vol.27, 1961, pp.1209-25, P.W. Kasteleyn.
• Propp, James (2004), Lambda-determinants and domino-tilings, arXiv:math.CO/0406301.

PDF version: Lambda-determinants and domino-tilings

• The Games and Puzzles Journal, No.14, 1996, pp.204-5, Robin J. Chapman, University of Exeter
• Domino Tilings and Products of Fibonacci and Pell numbers, Journal of Integer Sequences, Vol.5, 2002, Article 02.1.2, James A. Sellers, The Pennsylvania State University
• The Penguin Dictionary of Curious and Interesting Numbers, revised ed., 1997, ISBN 0-14-026149-4, David Wells, p.182.
• Thurston, W. P. (1990). "Conway's tiling groups". American Mathematical Monthly. 97 (8): 757–773.

External links

• R. Kenyon and A. Okounkov, What is ... a dimer?
• (sequence A004003 in the OEIS)