Alternating-Sign Matrices and Domino Tilings (Part I)

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.