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

lib/config.php:156: Notice: Undefined variable: accept

lib/DbaDatabase.php:154: Warning: dba_optimize() [<a href='function.dba-optimize'>function.dba-optimize</a>]: You cannot perform a modification to a database without proper access