JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 1, No 3 (1992)

Noam Elkies , Greg Kuperberg , Michael Larsen and James Propp

We continue the study of the family of planar regions dubbed Aztec diamonds in our earlier article and study the ways in which these regions can be tiled by dominoes. Two more proofs of the main formula are given. The first uses the representation theory of GL( n). The second is more combinatorial and produces a generating function that gives not only the number of domino tilings of the Aztec diamond of order n but also information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Lastly, we explore a connection between the combinatorial objects studied in this paper and the square-ice model studied by Lieb.

1. R.J. Baxter, Exactly Solved Models in Statistical Mechanics, Academic Press, San Diego, CA, 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," /. Combin. Theory A S3 (1990), 183-208.
4. C. Fan and F.Y. Wu, General lattice model of phase transitions, Phys. Rev. B 2 (1970), 723-733.
5. J.A. Green, Polynomial Representations of GLn, Springer Lecture Notes in Mathematics, Vol. 830, Springer-Verlag, Berlin, 1980.
6. W. Jockusch, "Perfect matchings and perfect squares," J. Combin. Theory A, to appear.
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 Phsyics, F. Harary, ed,, Academic Press, San Diego, CA, 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, problem 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," J. Combin. Theory A 34 (1983), 340-359.
14. J.K. Percus, Combinatorial Methods, Courant Institute of Mathematical Sciences, 1969.
15. G. P61ya and S. Szego, Problems and Theorems in Analysis, Vol. H, Springer, New York, 1976, p. 134, problem 132.
16. D.P. Robbins, ”The story of 1, 2, 7, 42, 429, 7436, ...," Math. Intelligencer 13(2) (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, Enumerative Combinatorics, Vol. I. Brooks-Cole, Belmont, MA, 1986.
20. R. Stanley, "A baker's dozen of conjectures concerning plane partitions," in Combinatoire Enumerative, Springer Lecture Notes in Mathematics, Vol. 1234, (G. Labelle and P. Leroux, eds.), Springer-Verlag, Berlin, 1986, pp. 285-293.
21. W. Thurston, "Conway's tiling groups," Amer. Math. Monthly 97 (1990), 757-773.
22. T. Ibkuyama, "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," doctoral thesis, Massachusetts Institute of Technology, Cambridge, MA, submitted.