Problem：

Count the ways to tile an MxN rectangle with 1x2 dominos.

Solve：

The number of ways to tile an MxN rectangle with 1x2 dominos is

2^(M*N/2) times the product of

{ cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4)

over all m,n in the range 0<m<M+1, 0<n<N+1.


[Exercises:

0) Why does this work for M*N odd?

1) When M<3 the count can be determined directly;

check that it agrees with the above formula.

2) Prove directly this formula gives an integer for all M,N, and further show that

 if M=N it is a perfect square when 4|N and twice a square otherwise.

]

Where does this come from?  For starters note that, with the usual checker-

board coloring, each domino must cover one light and one dark square.  Assume

that M*N is even (but as it happens our formula will work also when both

M,N are odd --- see exercise 0 above).  Form a square matrix of size

M*N/2 whose rows and columns are indexed by the light and dark squares,

and whose (j,k) entry is 1 if the j-th light and k-th dark square are

adjacent and zero otherwise.  There are now three key ideas:

First, the number of tilings is the number of ways to match each light

square with an adjacent dark square; thus it is the _permanent_ of our

matrix (recall that the permanent of a rxr matrix is a sum of the same

r! terms that occur in its determinant, except without the usual +1/-1

sign factors).

Second, that by modifying this matrix slightly we can convert the

permanent to a determinant; this is nice because determinants are generally

much easier to evaluate than permanents.  One way to do this is to replace

all the 1's that correspond to vertical adjacency to i's, and multiply the

whole thing by a suitable power of i (which will disappear when we raise

it to a fourth power).


[Exercise 3: check that this transformation actually works as advertised!]


Third, that we can diagonalize the resulting matrix A --- or, more

conveniently, the square matrix of A' order M*N whose order-(M*N/2)

blocks are 0,A;A-transpose,0 , whence det(A') = +-(det(A))^2.  Then

the rows and columns of A' are indexed by squares of either hue on our

generalized checkerboard, and its entries are 1 for horizontally adjacent

squares, i for vertically adjacent ones, and 0 for nonadjacent (including

coincident) squares.  This A' can be diagonalized by using the trigonometric

basis of vectors v_ab (a,b as in the formula above) whose coordinate at

the (m,n)-th square is  sin(a*m*pi/(M+1)) * sin(b*n*pi/(N+1)).


Exercise 4: verify that these are in fact orthogonal eigenvectors of A',

determine their eigenvalues, and complete the proof of the above formula.



(None of this is new, but it does not seem to be well-known: indeed

each of the above steps seems to have been discovered independently

several times, and I'm not sure whom to credit with the first discovery

of this particular application of the method.  For different approaches

to exactly solvable problems involving the enumeration of domino tilings,

see the two papers of G.Kuperberg, Larsen, Propp and myself on

"Alternating-Sign Matrices and Domino Tilings" in the first volume of

the _Journal of Algebraic Combinatorics_.)

--Noam D. Elkies (elkies@zariski.harvard.edu)

Dept. of Mathematics, Harvard University

http://www.faqs.org/faqs/puzzles/archive/geometry