Domino tiling Facts for Kids

A domino tiling of an 8×8 square

In geometry, 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 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.

Height functions
Thurston's height condition
Counting tilings of regions
Tatami
Degenerated space-filling curves
See also

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

More details can be found in .

Thurston's height condition

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.

Counting tilings of regions

A domino tiling of an 8×8 square using the minimum number of long-edge-to-long-edge pairs (1 pair in the center). This arrangement is also a valid Tatami tiling of an 8x8 square, with no four dominoes touching at an internal point.

The number of ways to cover an $m \times n$ rectangle with $\frac{mn}{2}$ dominoes, calculated independently by and , is given by

\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 $2\times n$ rectangle with n dominoes: the sequence reduces to the Fibonacci sequence (sequence A000045 in OEIS) (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 $mn \times mn$ 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.

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

Tatami

Tatami are Japanese floor mats in the shape of a domino (1x2 rectangle). They are used to tile rooms, but with additional rules about how they may be placed. In particular, typically, junctions where three tatami meet are considered auspicious, while junctions where four meet are inauspicious, so a proper tatami tiling is one where only three tatami meet at any corner ( Mathar 2013; Ruskey & Woodcock 2009). The problem of tiling an irregular room by tatami that meet three to a corner is NP-complete (Erickson & Ruskey 2013).

Degenerated space-filling curves

Any finite set of cells forming regular square grid n×n can be indexed by a selected Space-filling curve that is consistent with squares (that do a recursive four-partition of the quadrilateral unit grid), with an index i ranging from 0 to n²-1. Geometrically, the curve can be drawn as a path through the center of the square cells. A domino tiling is obtained by merging neighboring cells. The index j of each domino will be obtained by the function j=floor(i ÷ 2) of the original grid index. The new fractal curve is a "degenerated curve" because is another fractal. Examples:

The "degenerated Morton space-filling curve" produces a regular horizontal-oriented domino tiling; the curve is related with Geohash indexing, where the Z-shape curve is transformed into a И-shape curve.

The "degenerated Hilbert space-filling curve" produces an aperiodic tiling system, mixing horizontal- and vertical-oriented dominoes, 50% of each orientation. The degenerated Hilbert curve is isomorphic to the Munkres's fractal.

Domino tiling facts for kids

Contents

Height functions

Thurston's height condition

Counting tilings of regions

Tatami

Degenerated space-filling curves

See also