Domino tiling

In

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

Thurston's height condition

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).}$$

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.^[1]

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

These numbers can be found by writing them as the Pfaffian of an ${\displaystyle mn\times mn}$

• 
  An Aztec diamond of order 4, which has 1024 domino tilings
• 
  One possible tiling

Tatami

There is a one-to-one correspondence between a periodic domino tiling and a ground state configuration of the fully-frustrated Ising model on a two-dimensional periodic lattice.^[4] To see that, we note that at the ground state, each plaquette of the spin model must contain exactly one frustrated interaction. Therefore, viewing from the dual lattice, each frustrated edge must be "covered" by a 1x2 rectangle, such that the rectangles span the entire lattice and do not overlap, or a domino tiling of the dual lattice.

See also

• Gaussian free field, the scaling limit of the height function in the generic situation (e.g., inside the inscribed disk of a large Aztec diamond)
• Mutilated chessboard problem, a puzzle concerning domino tiling of a 62-square area of a standard 8×8 chessboard (or checkerboard)
• Statistical mechanics

Notes

References