Before this: Parity, Graphs, The transfer matrix.

A domino is two unit squares that share a side, lying flat or standing up. A tiling of a region of the square grid covers every cell of the region with dominoes, each cell exactly once, no two dominoes overlapping and none sticking out. In the language of graphs, make every cell a vertex and join two cells that share a side; a tiling is then a perfect matching, a set of edges that touches every vertex exactly once. Physicists call such a matching a dimer covering, and Kenyon 2009 is a set of lectures on it.

Colour the grid like a chessboard, a cell black or white by the parity of the sum of its coordinates. Every domino covers one cell of each colour, so a region with more cells of one colour than the other has no tiling at all. The mutilated chessboard is the classic case: cut two opposite corners off an 8 by 8 board and 62 cells remain, an even number, but both corners have the same colour, so 30 cells of one colour face 32 of the other and no tiling exists. The other way round, cut one black and one white cell from the full board and a tiling always exists. A rook can tour all 64 cells and come back to its start, and along that loop the colours alternate, so the two cut cells split the loop into two runs, each starting and ending on cells of opposite colours and so of even length; pair each run off two cells at a time.

The strip of height 2 counts the Fibonacci numbers. The left end of a 2 x n strip is covered either by one standing domino, leaving a 2 x (n-1) strip, or by two flat ones on top of each other, leaving a 2 x (n-2) strip, so the counts obey T(n) = T(n-1) + T(n-2) and run 1, 2, 3, 5, 8, 13. That is a transfer matrix at work: read the strip column by column and record which cells of the next column are already covered by flat dominoes poking in from the left. A strip of height m has 2^m such states, a tiling is a walk through them that starts and ends with nothing poking out, and for m = 2 the table is [[1, 1], [1, 0]], whose powers are the Fibonacci numbers.

For a region in the plane there is a much better way, one determinant. Write a matrix K with a row for each black cell and a column for each white one, and put a 1 or a -1 wherever the two cells share a side. Expanding det K gives one term for each way of pairing every black cell with a white neighbour, which is one term for each tiling, but with signs. Kasteleyn's theorem says the signs can be chosen to make every term the same sign: if each face of the graph with a multiple of 4 edges has an odd number of -1 edges round it, and each face with 2 more than a multiple of 4 has an even number, then the number of tilings is abs(det K) (Kenyon 2009, sections 3.3 and 3.4). On the square grid every face is a square of 4 edges, so one -1 on each is enough, and putting -1 on the standing edges of every other column does it. A determinant of side N takes about N^3 steps, so the count is quick even when the tilings are astronomically many. The theorem is named for Kasteleyn 1961, which counts the dimer arrangements on the square lattice. A planar graph that is not two-coloured needs a Pfaffian, a square root of the determinant of a skew-symmetric matrix, in place of the determinant.

The rectangle has a closed form. Weight the flat edges 1 and the standing edges i; the matrix of the whole grid, black and white cells together, is then a sum of Kronecker products of the matrices of two paths, its eigenvectors are products of sine waves, one along each side, with eigenvalues 2 cos(pi j/(m+1)) + 2i cos(pi k/(n+1)), and the count is the square root of the absolute value of their product. Pairing up the factors leaves T(m, n) = prod_(j=1..ceil(m/2)) prod_(k=1..ceil(n/2)) (4 cos^2(pi j/(m+1)) + 4 cos^2(pi k/(n+1))). For the 8 by 8 board that is 12988816 tilings. For a large rectangle log T(m, n) / (m n) tends to G/pi = 0.291561..., where G = 1 - 1/9 + 1/25 - 1/49 + ... = 0.915966... is Catalan's constant, so each cell adds a factor of about e^(G/pi) = 1.3385 to the count.

The Aztec diamond of order n is the staircase diamond of all cells lying inside abs(x) + abs(y) <= n + 1, with rows of 2, 4, up to 2n cells and back down, 2n(n+1) cells in all. Elkies, Kuperberg, Larsen and Propp 1992 prove that it has exactly 2^(n(n+1)/2) tilings. One of their proofs is domino shuffling, which grows a tiling of order n - 1 into one of order n: take out every 2 by 2 block whose two dominoes would run into each other, slide each remaining domino one step up, down, left or right as its colour says, and the empty cells of the larger diamond fall into 2 by 2 blocks, each filled with two parallel dominoes. Done with care, the steps pair the tilings of order n with the strings of n(n+1)/2 bits, which is where the power of 2 comes from; done with a fair coin for every block, they draw a tiling of the diamond uniformly at random.

A random tiling of a large Aztec diamond is not uniform to look at. Jockusch, Propp and Shor 1998 prove that, for all but a vanishing share of the tilings, the dominoes in the four corners line up with their neighbours like bricks in a wall, while in the middle the two directions mix, and the boundary between them tends to the circle of radius n/sqrt 2 inscribed in the diamond, the arctic circle. The figure is one tiling of the diamond of order 32 drawn by shuffling with coins from a fixed seed, 1056 dominoes on 2112 cells, flat ones blue and standing ones yellow. The top and bottom corners are frozen into flat brick walls, the left and right corners into standing ones, and the mixed middle fills the circle.

The name dimer comes from physics: a dimer is a molecule of two atoms, and a crystal surface packed with them, each on two neighbouring sites, is a tiling of the lattice of sites. Giving each edge a weight and each covering the product of the weights of its edges makes the dimer model of statistical mechanics, with the sum of all those products as its partition function; on the honeycomb lattice the coverings are tilings by rhombi, and chemists count them as the Kekule structures of a molecule. A tiling of a region with no holes is also a surface: its height function gives every corner of the grid an integer that steps by one along each side of a cell that no domino straddles, so a random tiling is a random surface, and in the frozen corners of the diamond that surface is a flat plane (Kenyon 2009, sections 1.3 and 2.2).

In the tree

Dimers on a design tiles the levels of the plane designs of the tree with dominoes and counts the ways.