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.