JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 1, No 2 (1992)

Noam Elkies , Greg Kuperberg , Michael Larsen and James Propp

We introduce a family of planar regions, called Aztec diamonds, and study tilings of these regions by dominoes. Our main result is that the Aztec diamond of order n has exactly 2 ^{n( n+1)/2} domino tilings. In this, the first half of a two-part paper, we give two proofs of this formula. The first proof exploits a connection between domino tilings and the alternating-sign matrices of Mills, Robbins, and Rumsey. In particular, a domino tiling of an Aztec diamond corresponds to a compatible pair of alternating-sign matrices. The second proof of our formula uses monotone triangles, which constitute another form taken by alternating-sign matrices; by assigning each monotone triangle a suitable weight, we can count domino tilings of an Aztec diamond.

1. R.J. Baxter, Exactly Solved Models in Statistical Mechanics, Academic Press, New York, 1982.
2. E.F. Beckenbach, ed., Applied Combinatorial Mathematics, John Wiley, New York, 1964.
3. J.H. Conway and J.C. Lagarias, "Tilings with polyominoes and combinatorial group theory," J. Combin. Theory Ser. A 53 (1990), 183-208.
4. C. Fan and F.Y. Wu, "General lattice model of phase transitions," Phys. Rev. B2 (1970), 723-733.
5. J.A. Green, Polynomial Representations of GLn, Lecture Notes in Mathematics 830, Springer, Berlin, 1980.
6. W. Jockusch, "Perfect matchings and perfect squares," Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1992.
7. P.W. Kasteleyn, "The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice," Physica 27 (1961), 1209-1225.
8. P.W. Kasteleyn, "Graph theory and crystal physics," in Graph Theory and Theoretical Physics, F. Harary, ed., Academic Press, New York, 1967, pp. 43-110.
9. E. Lieb, "Residual entropy of square ice," Phys. Rev. 162 (1967), 162-172.
10. L. Lovasz, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979, prob. 4.29.
11. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979.
12. W.H. Mills, D.P. Robbins, and H. Rumsey, Jr., "Proof of the Macdonald conjecture," Invent. Math. 66 (1982), 73-87.
13. W.H. Mills, D.P. Robbins, and H. Rumsey, Jr., "Alternating sign matrices and descending plane partitions," I Combin. Theory Ser. A 34 (1983), 340-359.
14. J.K. Percus, Combinatorial Methods, Courant Institute, New York, 1969.
15. G. P61ya and S. Szego, Problems and Theorems in Analysis, Vol. II, Springer, New York, 1976, prob. 132, p. 134.
16. D.P. Robbins, "The story of 1, 2, 7, 42, 429, 7436 " Math. Intelligencer 13 (1991), 12-19.
17. D.P. Robbins and H. Rumsey, Jr., "Determinants and alternating sign matrices," Adv. Math. 62 (1986), 169-184.
18. A.E. Spencer, "Problem E 2637," Amer. Math. Monthly 84 (1977), 134-135; solution published in 85 (1978), 386-387.
19. R. Stanley, "A baker's dozen of conjectures concerning plane partitions," in Combinatoire Enumerative, G. Labelle and P. Leroux, eds., Lecture Notes in Mathematics 1234, Springer- Verlag, Berlin, 1986, pp. 285-293. ELKIES, KUPERBERG, LARSEN, AND PROPP
20. R. Stanley, Enumerative Combinatorics, Vol. I. Wadsworth and Brooks/Cole, Belmont, MA, 1986.
21. W. Thurston, "Conway's tiling groups," Amer. Math. Monthly 97 (1990), 757-773.
22. T. Tokuyama, "A generating function of strict Gelfand patterns and some formulas on characters of general linear groups," J. Math. Soc. Japan 40 (1988), 671-685.
23. B.-Y. Yang, "Three enumeration problems concerning Aztec diamonds," Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1991.