New proof that the number of tilings for an Aztec diamond is 2^(n(n+1)/2)

by Eric Kuo

Throughout this proof, the term Aztec matching will represent a bipartite
matching for the graph representation of an Aztec diamond.  Thus to count
the number of tilings for an order n Aztec diamond is the same as counting
the number of order n Aztec matchings.

		T(n)=2*T(n-1)^2 / T(n-2)

We will show that the number of order n Aztec matchings is twice the square 
of the number of order n-1 Aztec matchings, divided by the number of order 
n-2 Aztec matchings.  Given the initial conditions that there are 2 order 1 
Aztec matchings and 8 order 2 Aztec matchings, we can recursively calculate 
the number of order n Aztec matchings. It easily follows by induction that 
the number of order n Aztec matchings is T(n) = 2^(n(n+1)/2).

We must show the inductive step. It is equivalent to show that

		T(n) * T(n-2) = 2 * T(n-1)^2

We superimpose an order n-2 Aztec matching on top of an order n Aztec 
matching. Here is an example for order 3 on top of order 5:

        X-X

      X-X X-X

    X X-O_O X-X
    |     |
  X X O-O O_O X-X
  |   ) )   |
X X O O-O O O O-X X
|   #     # ) )   |
X X O O-O O O-O X X
  |   ) )       |
  X X O O-O_O X X
    | |     | |
    X X O=O X X

      X-X X-X

        X-X

In this figure, O's represent the vertices shared by both the order 3 and
order 5 diamonds. X's represent vertices only in the order 5 diamond.
The edges in the matching for the order 5 are -, |, =, and #. The edges in
the matching for the order 3 are _, ),=, and #. Note that = and # represent
a double edge shared by both matchings. Also note that each X has degree one 
in the combined graph, while each O has degree two.

Now consider overlapping two order n-1 Aztec matchings in either of two ways 
(the example shown is for n-1=4):

Original order 4 aztec diamonds:

      A-A                 B_B

    A-A A-A             B B B_B
                        ) )
  A A-A A A-A         B B B B B B
  |     |             )     ) ) )
A A A-A A A A-A     B B B_B B B B B 
|         |         )             )
A A A-A A A A-A     B B B B_B B B B
  |     |             ) )     ) )
  A A A A A-A         B B B_B B B 
    | |
    A A A-A             B_B B_B 

      A-A                 B_B

The combined graphs:

        A-A                     X~X

      A-A A-A                 A-A B_B

    A A-O_O A-A             A-A O-O B_B
    |     |                     ) )
  A A O-O O_O A-A         A A-O O O-O B B
  |   ) )   |             |   ) |   ) ) )
X A O O-O O O O-A X     A A O-O O_O O-O B B
(   #     # ) )   (     |   )     |       )
X B O O_O O O-O B X     A A O-O O O_O-O B B
  )   | |       )         |   ) #     ) )
  B B O O_O-O B B         A A O O O=O B B
    ) )     ) )             | |
    B B O=O B B             A A O=O B_B

      B_B B_B                 A-A B_B

        B_B                     X~X

Each of these graphs can be partitioned into two order 4 Aztec
matchings plus two extra segments. The left graph was made by fitting
graph A to the top of the order 5 diamond and graph B to the bottom, and
adding the two side segments. The right graph was made by fitting graph A
to the left of the order 5 diamond and graph B to the right, and adding the
top and bottom segments.  In both cases, each O in the resulting graph has
degree two, while each A, B, and X has degree one. These graphs are like
the order 3 diamond matching on top of the order 5 matching.

In general, say we are given a graph G for an order n Aztec 
diamond whose inner vertices forming an order n-2 Aztec diamond have 
degree two, and whose other outer vertices have degree one.  We want to show
that the number of partitions of G into an order n Aztec matching
and an order n-2 Aztec matching is equal to the number of partitions of
that same graph into two order n-1 Aztec matchings with two line segments. 
That number is 2 to the number of cycles in G.  Since all cycles have even
length and are contained within the middle common vertices, we can partition
each cycle once and then determine which partition goes with which subgraph.
All doubled edges of G go to each subgraph.  It remains to show that the other 
edges are partitioned uniquely.

        X-X

      Y-C D-Y

    Y C-O-O D-Y
    |     |
  Y C O-O O-O D-Y
  |   | |   |
X C O O-O O O O-D X
|   #     # | |   |
X E O O-O O O-O F X
  |   | |       |
  Y E O O-O-O F Y
    | |     | |
    Y E O=O F Y

      Y-E F-Y

        X-X

>From the presence of the "Y" vertices, exactly one C, one D, one E, and one
F vertex will not be joined to a Y; all others must join to a Y.  Between 
those special vertices, there must be paths joining a C to a D and an E to 
an F, or from a C to an E and a D to an F.  Since each O has degree two, we 
cannot have paths from C to F and from D to E, otherwise the paths would 
intersect, forcing some degree of an O to be more than 2.

There are three kinds of "paths" from C to D: (1) a path that goes through
the interior O's; (2) a path of one segment, C-D; (3) C is connected to X,
thus forcing the adjacent X to connect with D. We'll call a path of type (1)
or (2) a continuous path.

Note that all vertices C and F have the same parity, and all vertices D and
E have the opposite parity from C and F.  Therefore any continuous path from
C to D, C to E, D to F, or E to F has odd length.  Thus both end segments of
a path (even for the C-X X-D path) must belong to the same matching in any 
partition of G.  When partitioning G into two matchings of order n and n-2,
the larger matching contains all the end segments.

Without loss of generality, let the paths in G connect C to D and E to F.
When G is partitioned into order n and order n-2 Aztec matchings, the 
segments containing C, D, E, and F must go into the order n matching.
G can also be partitioned into two order n-1 Aztec matchings, one matching
containing the end segments of C and D, the other containing the end segments
of E and F.  However, it is not possible to partition G into two n-1 Aztec 
matchings, one of which contains C and E, the other containing D and F.  The
reason is that since the CE matching must contain the E-end segment, it
must then contain the F-end segment, which can't happen, as F is not in that
Aztec matching.

Hence for each graph G, one can partition it into two order n-1 Aztec 
matchings in one way (left-right) or the other (top-bottom), but never both.
The partition of the paths are uniquely determined.

The number of ways to combine an order n and order n-2 matching is 
T(n)*T(n-2), while the number of ways to combine two order n-1 matchings
is 2*T(n-1)^2.  Each combination becomes such a graph G, so the relation
is proved.


Credits: I thank Henry Cohn for pointing out a similar relation noted
by Jim Propp in December 1993:

>Let a,b,c,d be four vertices forming a 4-cycle in the bipartite planar graph
>G, joined by edges that we will denote by ab, bc, cd, and da.  Then the
>proportion of matchings of G that have an alternating cycle at this face
>(i.e., the proportion of matchings of G that either contain edges ab and cd 
>or contain edges bc and da) is equal to
>	2 [p(ab) * p(cd)] + [p(bc) * p(da)]
>where p(.) denotes the proportion of matchings of G that contain the specified
>edge.

The proof that followed that statement gave me the idea for this new proof
of the Aztec tilings formula.