Keywords: algebraic combinatorics, permanent/determinant trick,
tilings, rhombic tilings, domino tilings, matching,
hexagonal systems, dominoes, perfect matchings,
counting matchings, plane partitions
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Article: 973 of sci.math.research
From: elkies@ramanujan.harvard.edu (Noam Elkies)
Subject: Re: Tiling/Combinatorics puzzle
Summary: There's some non-trivial math here!
Date: Sun, 30 May 1993 00:00:03 GMT
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Organization: Harvard Math Department
In article <1993May24.173049.16004@donau.et.tudelft.nl>
arlet@einstein.et.tudelft.nl (Arlet Ottens) writes:
>How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ?
12988816 = 3604^2
>Is there a general formula for larger squares ?
Yes. In fact there's a formula for rectangles: 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 0In article <1993May24.173049.16004@donau.et.tudelft.nl>
>arlet@einstein.et.tudelft.nl (Arlet Ottens) writes:
>>How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ?
>12988816 = 3604^2
...
>(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.
Of the four steps you mention, the only one discovered in this century
is the permanent-determinant method, which can be credited to
Kasteleyn, Fischer, Temperley, and Percus, roughly in that order. The
first three workers took a Pfaffian approach, initially to enumerate
exactly the same objects, domino tilings of rectangles. Later,
Kasteleyn generalized the method to an enumeration of matchings of an
arbitrary planar graph by a Pfaffian. Later still, Percus noticed that
permanents and determinants do the job just as well for bipartite
graphs. (Definition up to sign: The Pfaffian of an anti-symmetric
matrix is the square root of the determinant.)
>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_.)
I'm very glad you mentioned these papers, especially because of who
the authors are :-). Unfortunately, they do not treat the
permanent-determinant method in detail. I recommend this survey:
@incollection{kasteleyn:crystal,
author = "P. W. Kasteleyn",
booktitle = "Graph Theory and Theoretical Physics",
editor = "F. Harary",
publisher = "Academic Press",
title = "Graph theory and crystal physics",
year = 1967}
Finally, I'll follow Noam's tradition of giving really hard exercises:
"Exercise": Count the number of tilings of a regular hexagon by
rhombuses which consist of two unit equilateral triangles.
=============================================================================
Article: 980 of sci.math.research
From: elkies@ramanujan.harvard.edu (Noam Elkies)
Subject: Re: Tiling/Combinatorics puzzle
Date: Tue, 1 Jun 1993 16:56:53 GMT
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Organization: Harvard Math Department
> (Noam Elkies) writes:
>>In article <1993May24.173049.16004@donau.et.tudelft.nl>
>>arlet@einstein.et.tudelft.nl (Arlet Ottens) writes:
>>>How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ?
>>12988816 = 3604^2
>...
>>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_.)
>
>I'm very glad you mentioned these papers, especially because of who
>the authors are :-). Unfortunately, they do not treat the
>permanent-determinant method in detail.
True; sorry if my previous post did not make this clear.
By the way, the problem we considered in that paper is
enumerating domino tilings of figures like
X X
X X X X
X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X
X X X X
X X
Jim Propp found the answer (a power of 2 depending on the size of
the figure; for the above it's 2^10=1024) experimentally, but
it took a while to prove it. In our papers we finally gave several
proofs, each suggesting further work in different directions.
None of the proofs used the permanent/determinant transformation,
but an argument along these lines was found subsequently.
I should also point out another reference from the paper:
W. Jokusch, Perfect matchings and perfect squares, J. Combin. Theory A
(this was "to appear" in 1992, so it's probably appeared by now)
which gives a vast generalization of the fact that the number of
ways to tile an n*n by dominos is a square or twice a square
depending on the parity of n/2.
--Noam D. Elkies (elkies@zariski.harvard.edu)
Dept. of Mathematics, Harvard University
=============================================================================
Article: 978 of sci.math.research
From: gk00@midway.uchicago.edu (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Date: Mon, 31 May 1993 17:53:41 GMT
Organization: University of Chicago
Let me first take this opportunity to take back my catty comment about
Noam's exercises being really hard. He did break the analysis of
domino tilings of a rectangle into stages, which is a big hint.
There is a tradition in mathematics of "last year's thesis, next year's
problem set". However, in the best of the tradition, there are new
definitions and motivations to make the same question a lot easier.
To answer Alan Adler's question:
Allan Adler writes:
>How about triminoes, say, covering a board with r straight triminoes
>and s right triminoes?
No one knows, but I at least am pessimistic. The reason that Jim Propp
started looking at domino tilings (and planted the seed of the our
joint paper) is that he used a computer program to count them in small
cases and saw some interesting patterns. Without any theorems at one's
disposal, an "interesting pattern" in combinatorial enumeration usually
means that the size of some set of objects factors a lot. It's almost
the only pattern that's easy to see ab initio. By this principle, an
enumeration which is a simple sum, for example, might be unrecognizable
as such. C'est la vie.
As far as I know, concerning the problem of counting tilings of any
interesting region by triominoes, there are no interesting results
AND no one has noticed any interesting patterns. And furthermore,
if the problem is treated as an analogue of domino tilings, one of
the key steps is to convert the problem to counting matchings of
a planar graph. You can characterize the triomino problem as
counting "menage a trois" partitions subordinate to a certain hypergraph,
but the hypergraph isn't really planar, and even if it were, it's
a lot hore complicated than "menage a deux".
A more tractable question is: When does a region admit a tiling by
triominoes, say by r planks and s elbows? A pretty good method to
establish an answer of "no", which was recently generalized by Conway
and Lagarias, is to treat the region as a formal sum of its squares,
and ask if it is an integral combination of the triominoes. For an
answer of no, you can find a map from the abelian group generated by
the squares to Z or Z/n that annihilates all triominoes but does not
annihilate the region.
=============================================================================
Article: 984 of sci.math.research
From: gk00@midway.uchicago.edu (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Date: Wed, 2 Jun 1993 00:31:19 GMT
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Organization: University of Chicago
(Noam Elkies) writes:
>W. Jokusch, Perfect matchings and perfect squares, J. Combin. Theory A
>(this was "to appear" in 1992, so it's probably appeared by now)
I doubt it! How long did it take JCTA to publish your paper? Jockusch's
paper has conceivably appeared in the latest issue; it hadn't as of May.
I have an already-refereed paper waiting with JCTA and they told me
it would be 18 months.
>which gives a vast generalization of the fact that the number of
>ways to tile an n*n by dominos is a square or twice a square
>depending on the parity of n/2.
Per Noam's private request, here is one description following Jockusch
of what the number of tilings is a square or double-square of:
First, I need to define the residue and the sign of a tiling by
means of square moves, where a square move consists of switching
a pair of adjacent, horizontal dominoes to vertical. Every pair
of tilings is connected by a sequence of square moves and inverse
square moves. The residue (mod 4) of the all-horizontal tiling
is 0, it is constant under a square move away from the center of
the big square, and it increases by 1 under a square move at
the center of the square. A tiling is positive if its residue
is 0, negative if it is 2, and null if it is odd. If N is the
number of positive minus negative centrally-symmetric tilings,
then there are N^2 or 2N^2 tilings in all.
What's really going on is this: Given an arbitrary centrally-symmetric
planar graph whose central face has 8k+4 sides, a perfect matching also
has a residue r mod 4, and if the total of i^r over all
centrally-symmetric matchings is a+ib, then the total number of
matchings is a^2+b^2. If the graph additionally has a 4-fold
rotational symmetry, then either a=b or b=0, depending on a parity
condition.
=============================================================================
Article: 990 of sci.math.research
From: aigrain@cerise.irit.fr (Philippe AIGRAIN)
Subject: Re: Tiling/Combinatorics puzzle
Date: Thu, 3 Jun 1993 08:46:53 GMT
Organization: IRIT-UPS, Toulouse, France
(Greg Kuperberg) writes:
[stuff on counting tilings by triminoes deleted]
>A more tractable question is: When does a region admit a tiling by
>triominoes, say by r planks and s elbows? A pretty good method to
>establish an answer of "no", which was recently generalized by Conway
>and Lagarias, is to treat the region as a formal sum of its squares,
>and ask if it is an integral combination of the triominoes. For an
>answer of no, you can find a map from the abelian group generated by
>the squares to Z or Z/n that annihilates all triominoes but does not
>annihilate the region.
Claire and Richard Kenyon (respectively from ENS Lyon, France and Institut
Fourier, Grenoble, France) recently extended the Conway-Lagarias method
to give a definite answer to the question:
"Can a region without holes be tiled by a set of two rectangles - one k x l
and one l x k ?"
This result has been first presented at the 2nd Workshop on Polyominoes
and Tilings (ENS Lyon, June 1992) and later at FOCS'92.
Maurice Nivat and myself have also tried to extend a result on tilability
of convex regions by dominoes to triminoes (or any set of one vertical bar
and one horizontal bar of the same length). The result for tiling by dominoes
is as follows:
A convex region can be tiled by dominoes if and only if its diagonal
section are both 2-reducible.
Diagonal sections are the words of Zn built by intersecting the region by
successive diagonal lines and counting elements in each intersection.
A word of Zn is 2-reducible (resp. k-reducible) iff it is the additive
projection of a stack of couples (resp. k-uples) of 1. For instance,
1 3 3 1 is 2-reducible, 3 1 1 3 is not. This result was also presented
at the 2nd Workshop on Polyominoes and Tilings and at the 8th Summer
Conference on General Topology and its Applications (Queens College, NY,
June 1992)
We conjecture that a convex region is tilable by triminoes iff its
diagonal sections are both 3-reducible.
As a matter of fact, the 3rd Workshop on Polyominoes and Tilings will
be held at the Institut de Recherche en Informatique de Toulouse, France
January 20-21, 1994. Anyone interested to receive the call for participation
and communications to this unformal seminar should send me e-mail.
Philippe Aigrain
Institut de Recherche en Informatique de Toulouse
=============================================================================
Article: 995 of sci.math.research
From: sieda@hrz.uni-bielefeld.de ( Torsten Sillke)
Subject: Re: Tiling/Combinatorics puzzle
Date: Thu, 3 Jun 1993 16:57:18 GMT
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
Organization: Universitaet Bielefeld, Rechenzentrum
Another way to compute the number of domino tilings (perfect matchings)
of the n*m board (n*m grid). ([1, 2, 3, 4])
This method was used mainly for hexagonal systems, but can be used for
other graphs too [3].
[1] P. John, J. Rempel
Counting perfect matchings in hexagonal systems
in: Graphs, Hypergraphs and Applic.
Proc. of the Conference on Graph Theory ( Euba 84 ) 72-79
[2] P. John, H. Sachs
Calculating the Number of Perfect Matchings and of Spanning Trees,
Pauling's Orders, the Characteristic Polynomial, and the Eigenvectors
of a Benzenoid System
in: Topics in Current Chemistry, Vol 153, Springer (1990) 145-179
[3] K. A. Al-Khnaifes
Graphentheoretische Methoden zur Loesung Linearer Gleichungen und ihre
Anwendung auf Probleme inner- und ausserhalb der Graphentheory
Thesis TH Ilmenau (1988)
[4] H. Sachs
Perfect Matchings in hexagonal systems
Combinatorica 4 (1984) 89-99
[ Algorithm (faster than the usually max match for bipartite graphs).
Conjecture for a necessary and sufficient condition for a perfect
matching, which was disproved in [5].]
[5] Zhang Fu-ji, Chen Rong-si, Guo Xiao-fong
Perfect Matchings in Hexagonal Systems
Graphs and Combinatorics 1:4 (1985) 383-386
[ Proof of a necessary and sufficient condition for a perfect matching.
They give a counterexample to a conjecture of [4].]
[6] D.M. Cvetkovic, M. Doob, H. Sachs
Spectra on Graphs - theory and applic.
Academic Press, (1980)
[ for domino tilings see the chapter: Dimer Problem.
It gives an asymthotics too. ]
[7] R. C. Read
The dimer problem for narrow rectangular arrays: A unified method
of solution, and some extensions
Aequationes Mathematicae 24 (1982) 47-65
[ the variations include the triomino I3 (trimer) and diagonal dimers.]
[8] A. W. M. Dress, T. Sillke
Ueber Domino-Ueberdeckungen von Schachbrett- und aehnlichen Mustern
unpublished note, Bielefeld, (1984)
[ we had a necessary condition for
1) hexagonal systems: the one of H. Sachs [4]
2) domino tilings: the diagonal cuts of P. Aigrain (if I understand
him right.)
A non-tilable non-convex figure, which fullfills the diagonal criterium:
x x
x x x x
x x ]
[9] R. L. Graham, D. E. Knuth, O. Pataschnik;
Concrete Mathematics,
Addison Wessley, Reading (1994) 2nd Ed.
Chap. 7.1: Domino Theory and Change
[ The dimer problem for narrow rectangular arrays (width 2 and 3) ]
Problem 7.51: [ the dimer problem solved with eigenvalues ]
- M. E. Fisher;
Statistical mechanics of dimers on a plane lattice,
Physical Review 124 (1961) 1664-1672
- J. K. Percus;
Combinatorial Methods,
Springer Verlag, 1971
[ the dimer problem, pp 89-123 ]
- R. P. Stanley,
On dimer coverings of rectangles of fixed width,
Discrete Applied Mathematics 12 (1985) 81-87
- N. Elkies, G.Kuperberg, Larsen, Propp
"Alternating-Sign Matrices and Domino Tilings", 2 articles
Journal of Algebraic Combinatorics, 1
- W. Jokusch;
Perfect matchings and perfect squares,
J. Combin. Theory A, (1993?)
- G. Kuperberg;
Symmetries of Plane Partitions and the Permanent-Determinant Method,
Journal of Combinatorial Theory Series A (199??)
------------------------------------------------------
Example for the number of tilings of the 5x6 board:
Orient the edges of the 5x6 grid in the following way.
. <- p1 -> . <- p2 -> .
| | | | |
v v v v v
. -> . <- . -> . <- .
| | | | |
v v v v v
. <- . -> . <- . -> .
| | | | |
v v v v v
. -> . <- . -> . <- .
| | | | |
v v v v v
. <- . -> . <- . -> .
| | | | |
v v v v v
. -> v1 <- . -> v2 <- .
1
1 * 1 * * Number of pathes from p1 to v1 and v2
* 3 * 1 *
4 * 5 * 1
* 12 * 7 *
16 * 24 * 8
* 52 * 39 * <- 5x6 rectangle
68 * 115 * 47
* 235 * 201 * <- 5x8 rectangle
Number of perfect matchings = Abs Determinat M
M[i,j] = number of pathes from p[i] to v[j].
In the example 5x6:
[ 52 39 ]
M = [ ]
[ 39 52 ]
Det M = 1183
In the example 5x8:
[ 235 201 ]
M = [ ]
[ 201 235 ]
Det M = 14824
--------------------------------------------------------------
To answer the question of G. Kuperberg:
What is the number of tilings of a hexagon which rhombuses of unit
equilateral triangles?
Hexagon:
. . . . . . .
. . . . . . . . a hexagon with edgelengths (a,b,c)=(6,3,2)
. . . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . .
The opposite side has the same edgelength.
Number of rhombuses to tile: ab+bc+ac
S(a+b+c) S(a) S(b) S(c)
Number of tilings: -------------------------
S(a+b) S(a+c) S(b+c)
with S(n) = 0! 1! 2! ... (n-1)!
this is an easy exercise with the method of [1, 2, 3, 4],
as the number of paths are binomial coefficients, and the
determinant is easy to compute.
Asymtotics of S(n):
see Gradshteyn 8.333
or: Barnes, The Theory of the G-Function, Quarterly Math. 1900, 264-314
ln(S(x)) = x/2 ln(2 Pi) - ln(A) + 1/12 - 3/4 x^2 + (x^2/2 - 1/12)ln(x)
+ O(x^(-2))
with A = 1.28242713
Torsten Sillke
=============================================================================
Article: 999 of sci.math.research
From: gk00@midway.uchicago.edu (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Date: Fri, 4 Jun 1993 02:02:51 GMT
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
Organization: University of Chicago
( Torsten Sillke) writes:
> What is the number of tilings of a hexagon which rhombuses of unit
> equilateral triangles?
>
> . . . . . . .
> . . . . . . . . a hexagon with edgelengths (a,b,c)=(6,3,2)
> . . . . . . . . .
> . . . . . . . . .
> . . . . . . . .
> . . . . . . .
>
> S(a+b+c) S(a) S(b) S(c)
> Number of tilings: -------------------------
> S(a+b) S(a+c) S(b+c)
>
> with S(n) = 0! 1! 2! ... (n-1)!
>
> this is an easy exercise with the method of [1, 2, 3, 4],
> as the number of paths are binomial coefficients, and the
> determinant is easy to compute.
Pretty good! Let me up the ante in that case. Firstly,
MY determinant reduces to YOUR determinant :-). You are
taking the determinant of M_ij, the number of lattice paths from
the i'th edge at the top to the j'th edge at the bottom.
This is either an a x a, b x b, or c x c matrix, depending on how
you orient the hexagon. The machine tells you you get the same
determinant each time.
My matrix, A_tu, is indexed by the triangles, and has a 1 if the
triangles t and u are adjacent and a 0 otherwise. (The rows are
triangles pointing down and the columns are triangles pointing up by
convention.) It is a familiar observation that the permanent of A is
the number of tilings. In this case, permanent = determinant
(exercise).
If you have a matrix that has an entry of 1 that
look like this:
L | v
---+--
w | 1
where v is a column vector and w is a row vector, then the pivot
operation is to replace this matrix by L-wv. The pivot operation does
not change the determinant or the cokernel of the matrix as a
homomorphism from Z^n to Z^n (although it changes it to a map from
Z^(n-1) to Z^(n-1)). (The cokernel of a homomorphism is the quotient
of the target by the image.)
In the matrix A, each 1 entry corresponds to a single rhombus
somewhere in the hexagon. Claim: If you pivot A at every 1 which
corresponds to a vertical rhombus, the result is the matrix M up to
global sign.
Corollary: A and the three choices for M all have the same
determinant, as well as cokernels as maps of Z-modules.
Question: The integer cokernel of an integer matrix is an abelian
group whose cardinality is the determinant. Since the determinant in
this case counts tilings of a hexagon and has a nice form, what is the
cokernel?
All I know is that it can be presented by min(a,b,c) or fewer
generators, so if one of a,b, or c=1, it is cyclic. It is not always
cyclic.
Question: Since the cokernel is equinumerous with the set of
tilings, is there a natural bijection, or perhaps a linear isomorphism
between the vector spaces of formal linear combinations of elements
of the sets?
Historical note: The set of tilings of an a,b,c hexagon is
also the set of plane partitions in an a x b x c box, first enumerated
by Colonel Percy MacMahon circa 1900. The c x c determinant above
was found by Carlitz in the 60's, and perhaps by someone else earlier,
and a lattice-path approach very similar to the one described by
Torsten Sillke was found (independently?) by Gessel and Viennot.
=============================================================================
There is a bijection between the hexagonal tilings and the plane partitions [1].
[1] G. David, C. Tomei;
The problem of the calissons, AMM 96 (May 1989) 429-431
[ They give a bijection:
(n,n,n) hexagonal tilings <-> (n,n,n) plane partitions. ]
[2] F. Galvin
letter AMM 97 (1990) 131
[3] S. Kannan, Tiling Polygons with Parallelograms,
Discrete Computational Geometrie 7 (1992) 175-188
[A condition for tiling with parallelograms ]
[4] H. Pfeiffer, F. Romer;
Zerlegung von Regulaeren 2n-Ecken [in Rauten],
Elemente der Mathematik, 38:6 (1983) 157-159
[5]
Ein Zerlegungssatz fuer punktsymmetrische konvexe Vielecke,
Elemente der Mathematik, 38:6 (1983) 159
Torsten Sillke
=============================================================================
Article 1013 of sci.math.research:
From: gk00@midway.uchicago.edu (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Date: Thu, 10 Jun 1993 03:29:22 GMT
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
Organization: University of Chicago
In article sieda@hrz.uni-bielefeld.de ( Torsten Sillke) writes:
>>
>>Historical note: The set of tilings of an a,b,c hexagon is
>>also the set of plane partitions in an a x b x c box, first enumerated
>>by Colonel Percy MacMahon circa 1900. ....
>
>There is a bijection between the hexagonal tilings
>and the plane partitions [1].
As I like to say it, a hexagonal tiling is a picture of (the 3D Young
diagram of) a plane partition together with the back walls of its box.
________
/ /\ \
/___/ \___\
/\ \ / /\
/ \___\/___/ \
\ / /\ \ /
\/___/ \___\/
\ \ / /
\___\/___/
If I may toot my own horn a little (I know, I've been plenty verbose
and conspicuous here anyway), the program:
Plane partitions --> Tilings --> Determinant/Pfaffian --> Enumeration
was suggested to me by Jim Propp. I carried out the second step of
this program via the permanent-determinant method (and the
non-bipartite version, the Hafnian-Pfaffian method) for all ten
symmetry classes of plane partitions, and then grunged the third step
for many of the symmetry classes, including cyclically symmetric,
self-complementary plane partitions, equivalent to tilings invariant
under a rotation by 60 degrees. There is no other known enumeration of
this case. It's written up in my preprint
"Symmetries of Plane Partitions and the Permanent-Determinant Method"
which will appear in the Journal of Combinatorial Theory Series A some time
before the new millenium. Their backlog is the reason I'm mentioning
it again here. The answer, by the way, is that there are
( 1!4!7!...(3a-2)!/a!(a+1)!...(2a-1)! )^2
of them in a hexagon of size 2a, as conjectured by David Robbins. If
anyone here wants a reprint, I'll send it to you by hook or by crook
(i.e., by e-mail or paper mail, I haven't decided which) if you send me
a request with your paper mail address.
=============================================================================
Article 1197 of sci.math.research:
From: William.Jockusch@math.lsa.umich.edu (William Jockusch)
Subject: Re: domino tilings
Date: Mon, 16 Aug 1993 14:21:22 GMT
Organization: University of Michigan Engineering, Ann Arbor
>I was catching up on sci.math.research, and noticed the thread about
>counting domino tilings on squares and rectangles. My friend Eric
>Jensen counted some of these c. 1967, and noticed that the counts
>were squares or doubles of squares. He also counted domino tilings
>of *odd* squares and rectangles, which he made tilable by deleting
>the center square (making three different meanings of "square"!).
>I don't remember the pattern, but I think the counts for the holey
>odd squares were also squares or twice squares.
>
>Rich Schroeppel rcs@cs.arizona.edu
There is a theorem that if a bipartite plane graph has four-fold
rotational symmetry, the graph-theoretic distance between any vertex
and its 90-degree rotational image is odd, then the number of
matchings of the graph will be either a square or double a square
according to whether or not the number of vertices is a multiple of 8.
Because of the duality between domino tilings and perfect matchings,
this includes the situation you are talking about as a special case.
There is also a combinatorial interpretation for the square root in
terms of 2-factors of a "quotient graph" which is basically 1/4 of the
origional graph. (A 2-factor is the same thing as a matching, except
that you have TWO edges at every vertex. You are allowed have an edge
be a "double member" of the 2-factor.)
> What happens if you move the hole around?
The only fact I know of here is that IF you put the hole on the
outside of the square, it doesn't matter where on the outside you
put it -- as long as it is in the correct color-class (with the
chessboard coloring), the number of matchings will be the same.
I'm not sure who first noticed this.
Thanks to Wayne Goddard for bringing this string to my attention.
William Jockusch
=============================================================================
Subject: The Shape of a Typical Boxed Plane Partition
Date: 24 Sep 1998 18:50:22 GMT
From: mark@csc.albany.edu (Mark Steinberger)
Organization: The University at Albany
Newsgroups: sci.math.research
New Release
New York Journal of Mathematics 4 (1998), 137-165
Title: The Shape of a Typical Boxed Plane Partition
Authors: Henry Cohn, Michael Larsen, and James Propp
Date of Publication: September 23, 1998
Keywords: Plane partitions, rhombus tilings of hexagons, calculus of
variations, random tilings, limit laws for random structures
Subject Classification: Primary 60C05, 05A16; Secondary 60K35, 82B20
Abstract:
Using a calculus of variations approach, we determine the shape of a
typical plane partition in a large box (i.e., a plane partition chosen
at random according to the uniform distribution on all plane
partitions whose solid Young diagrams fit inside the box).
Equivalently, we describe the distribution of the three different
orientations of lozenges in a random lozenge tiling of a large
hexagon. We prove a generalization of the classical formula of
MacMahon for the number of plane partitions in a box; for each of the
possible ways in which the tilings of a region can behave when
restricted to certain lines, our formula tells the number of tilings
that behave in that way. When we take a suitable limit, this formula
gives us a functional which we must maximize to determine the
asymptotic behavior of a plane partition in a box. Once the
variational problem has been set up, we analyze it using a
modification of the methods employed by Logan and Shepp and by Vershik
and Kerov in their studies of random Young tableaux.
This paper's home page is http://nyjm.albany.edu:8000/j/1998/4-10.html
It contains links to the various graphical formats of the paper,
including pdf with numerous cross-reference links for ease of reading.
=============================================================================
math.CO/9810019 Theresia Eisenk\"olbl
Rhombus Tilings of a Hexagon with Two Triangles Missing on the Symmetry Axis
math.CO/9810091 Greg Kuperberg
An exploration of the permanent-determinant method
math.CO/9810143 Harald Helfgott, Ira M. Gessel
Enumeration of tilings of diamonds and hexagons with defects
math.CO/9904150
James Propp: Enumeration of Matchings: Problems and Progress
math.CO/9906102
Ilse Fischer: Enumeration of rhombus tilings of a hexagon which contain a
fixed rhombus in the centre
cond-mat/9906154
W. T. Lu, F. Y. Wu: Dimer statistics on the M\"obius strip and the Klein
bottle
the xxx Math Archive Front at http://front.math.ucdavis.edu/