Domino Tiling - Counting Tilings of Regions

Counting Tilings of Regions

The number of ways to cover an rectangle with dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), is given by

which is equivalent to

A special case occurs when either m (or symmetrically n) is set to 2: the sequence reduces to the Fibonacci sequence (Klarner & Pollack 1980).

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

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

These numbers can be found by writing them as the Pfaffian of an skew-symmetric matrix whose eigenvalues can be found explicitly. 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 statistical mechanics.

The number of tilings of a region is very sensitive to boundary conditions, and can change dramatically with apparently insignificant changes in the shape of the region. This is illustrated by the number of tilings of an Aztec diamond of order n, where the number of tilings is 2(n+1)n/2. If this is replaced by the "augmented Aztec diamond" of order n with 3 long rows in the middle rather than 2, the number of tilings drops to the much smaller number D(n,n), a Delannoy number, which has only exponential rather than super-exponential growth in n. For the "reduced Aztec diamond" of order n with only one long middle row, there is only one tiling.