×

Alternating-sign matrices and domino tilings. I. (English) Zbl 0779.05009

[For Part II see ibid., No. 3, 219-234 (1992).]
For a family of planar regions, called Aztec diamonds, the authors discuss tilings of these regions by dominoes. They prove in two ways that the Aztec diamond of order \(n\) has exactly \(2^{n(n+1)/2}\) domino tilings. Both proofs relate to alternating sign matrices (W. H. Mills, D. P. Robbins and H. Rumsey jun. [Alternating sign matrices and descending plane partitions, J. Comb. Theory, Ser. A 34, 340-359 (1983; Zbl 0516.05016)]). The authors also obtain more refined enumerative information (expressed in terms of generating functions) regarding certain natural statistics of such tilings.
Reviewer: E.Schulte (Boston)

MSC:

05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05B45 Combinatorial aspects of tessellation and tiling problems

Citations:

Zbl 0516.05016
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Total number of nodes in all labeled graphs on n nodes.

References:

[1] R.J. Baxter, Exactly Solved Models in Statistical Mechanics, Academic Press, New York, 1982. · Zbl 0538.60093
[2] E.F. Beckenbach, ed., Applied Combinatorial Mathematics, John Wiley, New York, 1964. · Zbl 0141.00103
[3] J.H. Conway and J.C. Lagarias, “Tilings with polyominoes and combinatorial group theory,” J. Combin. Theory Ser. A53 (1990), 183-208. · Zbl 0741.05019
[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. · Zbl 0451.20037
[6] W. Jockusch, “Perfect matchings and perfect squares,” Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1992. · Zbl 0808.05035
[7] P.W. Kasteleyn, “The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice,” Physica27 (1961), 1209-1225. · Zbl 1244.82014
[8] Kasteleyn, P. W.; Harary, F. (ed.), Graph theory and crystal physics, 43-110 (1967), New York · Zbl 0205.28402
[9] E. Lieb, “Residual entropy of square ice,” Phys. Rev.162 (1967), 162-172.
[10] L. Lovász, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979, prob. 4.29. · Zbl 0439.05001
[11] I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979. · Zbl 0487.20007
[12] W.H. Mills, D.P. Robbins, and H. Rumsey, Jr., “Proof of the Macdonald conjecture,” Invent. Math.66 (1982), 73-87. · Zbl 0465.05006
[13] W.H. Mills, D.P. Robbins, and H. Rumsey, Jr., “Alternating sign matrices and descending plane partitions,” J. Combin. Theory Ser. A34 (1983), 340-359. · Zbl 0516.05016
[14] J.K. Percus, Combinatorial Methods, Courant Institute, New York, 1969. · Zbl 0227.05003
[15] G. Pólya and S. Szegö, Problems and Theorems in Analysis, Vol. II, Springer, New York, 1976, prob. 132, p. 134. · Zbl 0338.00001
[16] D.P. Robbins, “The story of 1, 2, 7, 42, 429, 7436,...,” Math. Intelligencer13 (1991), 12-19. · Zbl 0723.05004
[17] D.P. Robbins and H. Rumsey, Jr., “Determinants and alternating sign matrices,” Adv. Math.62 (1986), 169-184. · Zbl 0611.15008
[18] A.E. Spencer, “Problem E 2637,” Amer. Math. Monthly84 (1977), 134-135; solution published in 85 (1978), 386-387.
[19] Stanley, R.; Labelle, G. (ed.); Leroux, P. (ed.), A baker’s dozen of conjectures concerning plane partitions, No. 1234, 285-293 (1986), Berlin · Zbl 0612.05008
[20] R. Stanley, Enumerative Combinatorics, Vol. I. Wadsworth and Brooks/Cole, Belmont, MA, 1986. · Zbl 0608.05001
[21] W. Thurston, “Conway”s tiling groups,“ <Emphasis Type=”Italic“>Amer. Math. Monthly <Emphasis Type=”Bold”>97 (1990), 757-773. · Zbl 0714.52007
[22] T. Tokuyama, “A generating function of strict Gelfand patterns and some formulas on characters of general linear groups,” J. Math. Soc. Japan40 (1988), 671-685. · Zbl 0639.20022
[23] B.-Y. Yang, “Three enumeration problems concerning Aztec diamonds,” Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1991.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.