The marriage theorem from the previous post provides a direct proof that the 8x8 square with two diagonal corners removed cannot be tiled by dominoes. However it is incapable in providing the number of possible tiling schemes if tiling solutions exist. The number is usually quite large.
However, in 1961, Kasteleyn and others actually found the exact solution for tiling a rectangle lattice with dominoes. The solution given by Kasteleyn involves the use of Pfaffian. Pfaffian is a special kind of matrices and less known to today's students. The problem of tiling rectangles itself is interesting for many physical and chemical problems, for example, the adsorption of diatomic molecules on a regular surface, the cell-cluster theory of liquds, the Ising problem (spin arrangement in two-dimensional lattice). Therefore the search for the exact solution and its asymptotic behaviour is not just for curiosity only but also driven by the real needs.
Here I sketch the main idea described by Kasteleyn. Anyone interested in knowing the details should read read the original paper, Physica, 1961, vol. 27, pp. 1209-25.
Consider a lattice, m x n, and m is even and n can be odd or even. (If both m and n are odd, it is obviouesly no tiling solution.) Each square at the lattice point can be labeled by {i (from 1 to m),j (from 1 to n)}. The square can also be uniquely labeled by just one number if an order is defined. For example, we can define a new label, p (from 1 to mxn )and p is related with {i,j} as follows,
{i,j} <--> p = (j-1)m + j.
We use p numbers to describe a configuration of dominoes, i.e. tiling scheme. First we consider a trivial configuration which is a solution for lattices. It can be drawn schematically as follows,
o-----o o-----o o-----o o-----o
{1,1} {2,1} {3,1}{4,1} {5,1}{6,1} {7,1}{8,1}
o-----o o-----o o-----o o-----o
{1,2} {2,2}
o-----o o-----o o-----o o-----o
{1,3} {2,3}
o-----o o-----o o-----o o-----o
{1,4} {2,4}
A configuration can be writen as a list, {{p1,p2},{p3,p4}, ... {p(nm-1), pnm}} and the above trivial configuration can be writen as, {{1,2},{3,4},...{nm-1, nm}}. However, if we exchange the order of each pair list, {pi,p{i+1)}, it still represents a same configuration. Or if we exchange of the order of child lists of the parent list, the configuration keeps too. Therefore, we need to define an order to eliminate such ambagiousness. One convention of the following can be adopted for the order,
p1 < p2; p3 < p4; ...; p(mn-1) < p(mn); and
p1 < p3 < p5 < ... < p(mn-1).
Such ordering relates the configuration with a Pfaffian. A Pfaffian is a number attributed to a triangular array of coefficients in the following way,
Pf[{a(i,j)|i,j=1,...N, N even}]= Sum[p[P]Permutation[a(k1,k2)a(k3,k4)...a(k(n-1),kn)]],
where p[P] (=1 or -1) is the parity of the permutation P and the sum runs over all possible permutations.
The number of dominoes' configuration is then given by Pf[D(p;p')]. The element of the matrix D(p;p') can be defined as follows. If there is no bonding between p and p' (not covered by the same domino), the element is 0. If the two are connected by a horizonal bond, the element is set as 1 and if connected by a vertical bond, the element could be 1 or -1. More exactly, the element is given by the following equations.
D(i,j;i+1,j)=1;
D(i,j;i,j+1)=(-1)^i;
D(i,j;i',j')=0, otherwise.
(If the dominoes are not symmetric, the corresponding nondegeneracy should be mulitplied.) The derivation of the first two rules needs a proof. The essential part of the proof lies in the transformation to construct any new configuration from the trivial configuration given above. 1) the sites with bond breaking and formation form polygons with alternating old and new bonds. 2) all the polygons do not overlap or cross. 3) by just moving the bonds of the polygons by just one bond distance, new configuration and old configuration can be exchanged.
Once the matrix D(p;p') is constructed, the next job is to calculate the Pfaffian. The following property can be used,
(Pf[D])^2 = det D,
where D is the skey-symmetric matrix extended from the triangular array of elements of the Pfaffian. The matrix can be decomposed in the following way,
D = Qm X En + Fm X Qn,
where En is the nxn unit matrix, and Q is the matrix in the following format, {{0,1,0,0,-...},{-1,0,1,0,0...},{0,-1,0,1,0},...} and F is the matrix in the following format, {{-1,0,0,0...},{0,1,0,0,...},{0,0,-1,0,...},...}. By diagonzation the above matrices product, the configuration number can be found.
Pf[D] = Product[Product[2(Cos[k Pi/(m+1)]^2 + Cos[l Pi/(n+1)]^2)^(1/2),{l,1,n}],{k,1,m/2}].
The above result could be further simplified slightly. For a simple calculation shows that the number of ways to tile a 8x8 lattice with dominoes is 12988816.
The result is quite surprsing. Since we know the answer must be an integer, yet it is given as the products of a series of irrational numbers. Kasteleyn also looked at the situation when perodic conditions are applied to the lattice, i.e. lattice on torus. More discussion could be given on the application of this result.
Note: On the ICM 2006 in Madrid, Spain, Andrei Okounkov has been awarded a Fields medal for his study on random tiling pattern.
