<<

. 7
( 14 .)



>>




40
1 4 6 1

3 8 3

2 5 4

7 2

5


Continue in this manner until all the numbers are removed from the
original SYT. The remarkable fact is that the exit numbers, read from top to
bottom, will now be n, n ’ 1, . . . , 1. We began with the exit numbers in the
order 1, 2, . . . , n, and each exit from the diagram transposed two adjacent
exit numbers. The size (number of entries) of the original SYT is equal to
n ( n ’ 1 ) / 2, which is the number of inversions of the permutation
n, n ’ 1, . . . , 1. Hence we have converted 1, 2, . . . , n to n, n ’ 1, . . . , 1 by
n(n’1)/2 adjacent transpositions, thereby de¬ning a reduced decomposition
of w0 . Edelman and Greene prove that this algorithm yields a bijection
between SYT of shape (n ’ 1, n ’ 2, . . . , 1) and reduced decompositions of
w0 . For the above example, the reduced decomposition is given by 12345 ’
13245 ’ 13425 ’ 14325 ’ 14352 ’ 41352 ’ 41532 ’ 45132 ’ 45312 ’
45321 ’ 54321.



7 Tilings.

The ¬nal enumerative topic we will discuss concerns the partitioning of some
planar or solid shape into smaller shapes. Such partitions are called tilings.
The combinatorial theory of tilings is connected with such subjects as geom-
etry, group theory, and logic, and has applications to statistical mechanics,
coding theory, and many other topics. Here we will be concerned with the
purely enumerative question of counting the number of tilings.



41
The ¬rst signi¬cant result about the enumeration of tilings was due to
the Dutch?? physicist P. W. Kasteleyn (1???“19??) and independently to
the British physicist Harold Neville Vazeille Temperley (b. 1931) and the
British-born physicist Michael Ellis Fisher (b. 1931). Motivated by work re-
lated to the adsorption of diatomic molecules on a surface and other physical
problems, they were led to consider the tiling of a chessboard by dominos
(or dimers). More precisely, consider an m — n chessboard B, where at least
one of m and n is even. A domino consists of two adjacent squares (where
“adjacent” means having an edge in common). The domino can be oriented
either horizontally or vertically. Thus a tiling of B by dominos will require
exactly mn/2 dominos, since there are mn squares in all, and each domino
has two squares. The illustration below shows a domino tiling of a 4 — 6
rectangle.




Let N (m, n) denote the number of domino coverings of an m — n chess-
board. For instance, N (2, 3) = 3, as shown by:




We have in fact that
N (2, n) = Fn+1 , (23)




42
where Fn+1 denotes a Fibonacci number, de¬ned by the recurrence

F1 = 1, F2 = 1, Fn+1 = Fn + Fn’1 .

To prove equation (23), we need to show that N (2, 1) = 1, N (2, 2) = 2,
and N (2, n + 2) = N (2, n + 1) + N (2, n). Of course it is trivial to check
that N (2, 1) = 1 and N (2, 2) = 2. In any domino tiling of a 2 — (n + 2)
rectangle, either the ¬rst column consists of a vertical domino, or else the
¬rst two columns consist of two horizontal dominos. In the former case we
are left with a 2 — (n + 1) rectangle to tile by dominos, and in the latter
case a 2 — n rectangle. There are N (2, n + 1) ways to tile the 2 — (n + 1)
rectangle and N (2, n) ways to tile the 2 — n rectangle, so the recurrence
N (2, n + 2) = N (2, n + 1) + N (2, n) follows, and hence also (23).

The situation becomes much more complicated when dealing with larger
rectangles, and rather sophisticated techniques such as the “transfer-matrix
method” or the “Pfa¬an method” are needed to produce an answer. The
¬nal form of the answer involves trigonometric functions (see Box), and it is
not even readily apparent (without su¬cient mathematical background) that
the formula gives an integer. It follows, however, from the subject known
as Galois theory that N (2n, 2n) is in fact the square or twice the square of
an integer, depending on whether n is even or odd. For instance, N (8, 8) =
12, 988, 816 = 36042 , while N (6, 6) = 6728 = 2 · 582 . It is natural to ask
for a combinatorial reason why these numbers are squares or twice squares.
In other words, in the case when n is even we would like a combinatorial
interpretation of the number M (2n) de¬ned by N (2n, 2n) = M (2n)2 , and
similarly when n is odd. While a formula for M (2n) was known making it
obvious that it was an integer (so not involving trigonometric functions), it
was only in 1992 that William Jockusch (19??“ ) found a direct combinatorial
interpretation of M (2n). In 1996 Mihai Adrian Ciucu (b. 1968) found an even
simpler interpretation of M (2n) as the number of domino tilings of a certain
region Rn , up to a power of two. The region Rn is de¬ned to be the board
consisting of 2n ’ 2 squares in the ¬rst three rows, then 2n ’ 4 squares in
the next two rows, then 2n ’ 6 squares in the next two rows, etc., down to
two squares in the last two rows. All the rows are left-justi¬ed. The board
R4 is illustrated in Figure 5.

If T (n) denotes the number of domino tilings of Rn , then Ciucu™s formula

43
Figure 5: The board R4 .

states that
N (2n, 2n) = 2n T (n)2 .
If n is even, say n = 2r, then N (2n, 2n) = (2r T (n))2 , while if n is odd,
say n = 2r + 1, then N (2n, 2n) = 2(2r T (n))2 , so we recover the result that
N (2n, 2n) is a square or twice a square depending on whether n is even or
odd.




BOX. Kasteleyn™s formula for the number N (2m, 2n) of domino tilings
of a 2m — 2n chessboard:
m n
sπ tπ
mn
cos2 + cos2
N (2m, 2n) = 4 .
2m + 1 2n + 1
s=1 t=1




44
Although the formula for the number of domino tilings of a chessboard
is rather complicated, there is a variant of the chessboard for which a very
simple formula for the number of domino tilings exists. This new board
is called an Aztec diamond, and was introduced by Noam David Elkies (b.
1966), Gregory John Kuperberg (b. 1967), Michael Je¬rey Larsen (b. 1962),
and James Gary Propp (b. 1960). Their work has stimulated a ¬‚urry of
activity on exact and approximate enumeration of domino tilings, as well as
related questions such as the appearance of a “typical” domino tiling of a
given region.

The Aztec diamond AZn of order n consists of two squares in the ¬rst
row, four squares in the second row beginning one square to the left of the
¬rst row, six squares in the third row beginning one square to the left of the
second row, etc., up to 2n squares in the nth row. Then re¬‚ect the diagram
created so far about the bottom edge and adjoin this re¬‚ected diagram to
the original. For instance, the Aztec diamond AZ3 looks as follows:




Let az(n) be the number of domino tilings of the Aztec diamond AZn .
For instance, AZ1 is just a 2 — 2 square, which has two domino tilings (both
dominos horizontal or both vertical). Hence az(1) = 2. It™s easy to compute
by hand that az(2) = 8, and a computer reveals that az(3) = 64 = 26 ,
az(4) = 1024 = 210 , az(5) = 32768 = 215 , etc. The evidence quickly becomes



45
overwhelming for the conjecture that
1
az(n) = 2 2 n(n+1) . (24)

It is rather mysterious why Aztec diamonds seem to be so much more nicely
behaved regarding their number of domino tilings than the more natural
m — n chessboards.

A proof of the conjecture (24) is the main result of Elkies et al. mentioned
above. They gave four di¬erent proofs, showing the surprising connections
between Aztec diamonds and various other branches of mathematics. (For
1
instance, it is not a coincidence that 2 2 n(n+1) is the degree of an irreducible
representation of the group GL(n + 1, C).) Of course a combinatorialist
would like to see a purely combinatorial proof, and indeed Elkies et al. gave
such proofs. Other combinatorial proofs have been since given by Ciucu
and Propp. We will sketch the fourth proof of Elkies et al., called a proof
by domino shu¬„ing. The domino shu¬„ing procedure we describe will seem
rather miraculous, and there are many details to verify to see that it actually
works as claimed. Nevertheless, we hope that our brief description will take
some of the mystery out of equation (24).

We ¬rst color the squares of the Aztec diamond AZn black and white in
the usual chessboard fashion, with the ¬rst (leftmost) square in the top row
colored white. Here is a tiling of AZ3 with the chessboard coloring shown.




46
Each domino will have one white square and one black square. There are
four possible colorings and orientations of a domino, shown in the illustration
below. With each of these four possible colored dominos we associate a
direction: up, down, right, and left, as indicated below by an arrow.




We can enlarge the Aztec diamond AZn to AZn+1 by adding squares
around the boundary. Add one square at the beginning and one square at
the end of each row, and two squares at the top and bottom. The next
illustration shows the earlier tiling of AZ3 , with an arrow placed on each
domino according to its coloring and orientation, and the boundary of new
squares to give AZ4 . We have also numbered each domino for later purposes.


47
16

26 3 4
 -
5 6? 7
 -
8 9? 10
 -
11 12
 -




Now move each domino one unit in the direction of its arrow. This is
the shu¬„ing operation referred to in the name “domino shu¬„ing.” It can
be shown that (a) the dominos do not overlap after shu¬„ing, and (b) the
squares of AZn+1 that are not covered by dominos can be uniquely covered
with exactly n + 1 2 — 2 squares. The next ¬gure shows the dominos after
shu¬„ing (with the same numbers as before), together with the leftover four
2 — 2 squares.




48
1

2

3 4

5 7

8 6 10

11 9 12




We now complete the partial tiling of AZn+1 to a complete tiling by
putting two dominos in each 2 — 2 square. There are of course two ways to
tile a 2 — 2 square, so there are 2n+1 ways to tile all n + 1 of the 2 — 2 squares.
Therefore we have associated 2n+1 tilings of AZn+1 with each tiling of AZn .
The amazing fact is that every tiling of AZn+1 occurs exactly once in this
way! In other words, given a tiling of AZn+1 , we can reconstruct which of
the dominos were shu¬„ed from a tiling of AZn and thus also the n + 1 2 — 2
squares that were left over. Since there are exactly 2n+1 tilings of AZn+1
associated with each tiling of AZn , we obtain the recurrence

az(n + 1) = 2n+1 az(n).

The unique solution to this recurrence satisfying az(1) = 2 is easily seen (for
instance by mathematical induction) to be

<<

. 7
( 14 .)



>>