From: greg@math.ucdavis.edu (Greg Kuperberg)
Subject: Re: Tiling a square with dominos
Date: 15 Aug 2000 15:40:02 -0700
Newsgroups: sci.math.research
Summary: [missing]

In article <3999AFB0.1346@club-internet.fr>,
Pierre Bornsztein  <pbornszt@club-internet.fr> wrote:
>Suppose you want to tile a 2^n * 2^n square with dominos 1*2.
>
>Let c(n) be the number of ways to do such a tiling (the square is
>oriented, so you don't have to look at the rotations or symmetries).
>
>For example, it is easy to see that we have 
>(1/n)*Ln(Ln(c(n))) --> Ln(4)  as n --> +oo

>What are the best known bounds for c(n) (with references...)?

Kasteleyn, Temperley, and Fisher gave an exact formula for the number
of domino tilings of an arbitrary rectangle. Kasteleyn's article is

@article{Kasteleyn:quadratic,
    author = "P. W. Kasteleyn",
    title = "The statistics of dimers on a lattice {I}.  The number of
        dimer arrangements on a quadratic lattice",
    journal = "Physica",
    volume = 27,
    pages = "1209--1225",
    year = 1961}

In particular they showed that if N(a,b) is the number of tilings of an
a x b rectangle, then

    ln(N(a,b))/ab -> G/pi

where

    G = 1 - 1/9 + 1/16 - ...

is Catalan's constant, if both a and b go to infinity.  In particular,

    ln(c(n))/4^n -> G/pi.  

The main idea is a tool due to Kasteleyn (and simplified by Percus in
the bipartite case) called the permanent-determinant method:  The number
of matchings of any bipartite graph can be (tautologically) expressed
as a permanent.  If the graph is planar, you can change the signs of
the entries to convert the permanent to a determinant.  You can easily
diagonalize the matrix if the graph is a rectangular grid.  An on-line
reference is:

    http://www.mathsoft.com/asolve/constant/catalan/dimer.html

Another interesting fact is that number of domino tilings of a square
is always a square or twice a square.  William Jockusch found a very
general reason for this:  It holds for the number of matchings of any
bipartite planar graph with a 4-fold rotational symmetry that exchanges
the colors.  A more general study of the role of symmetry in enumeration
of matchings and the permanent-determinant method is in my arXiv article
math.CO/9810091.
-- 
  /\  Greg Kuperberg (UC Davis)
 /  \
 \  / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/
  \/  * All the math that's fit to e-print *