Domino tiling

From Wikipedia, the free encyclopedia

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

1 Thurston's height condition
2 Counting tilings of squares
3 See also
4 References
5 External links

[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.

[edit] Counting tilings of squares

The number of ways to cover a $2 n$ -by- $2 n$ square with $2 n 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 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

Dimer covering
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

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 .

Propp, James (2005), “Lambda-determinants and domino-tilings”, Advances in Applied Mathematics 34 (4): 871–879, arXiv:math.CO/0406301, DOI 10.1016/j.aam.2004.06.005 .