In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect 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.

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 vertices of the grid. For instance, draw a chessboard, fix a node ${\displaystyle A_{0}}$ with height 0, then for any node there is a path from ${\displaystyle A_{0}}$ to it. On this path define the height of each node ${\displaystyle A_{n+1}}$ (i.e. corners of the squares) to be the height of the previous node ${\displaystyle A_{n}}$ plus one if the square on the right of the path from ${\displaystyle A_{n}}$ to ${\displaystyle A_{n+1}}$ is black, and minus one otherwise.

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

William Thurston (1990) describes a 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. A necessary condition for this region to be tileable is that this path must close up to form a simple closed curve in three dimensions, however, this condition is not sufficient. Using more careful analysis of the boundary path, Thurston gave a criterion for tileability of a region that was sufficient as well as necessary.

The number of ways to cover an ${\displaystyle m\times n}$ rectangle with ${\displaystyle {\frac {mn}{2}}}$ dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), is given by $${\displaystyle \prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right)}$$ (sequence A099390 in the OEIS).

When both m and n are odd, the formula correctly reduces to zero possible domino tilings.

A special case occurs when tiling the ${\displaystyle 2\times n}$ rectangle with n dominoes: the sequence reduces to the Fibonacci sequence.

Another special case happens for squares with m = n = 0, 2, 4, 6, 8, 10, 12, ... is