Domino tilings with barriers. (English) Zbl 0948.05020

Propp, James; Stanley, Richard

J. Comb. Theory, Ser. A 87, No. 2, 347-356 (1999).

An Aztec diamond of order \(n\) is a region composed by \(2n(n+1)\) unit squares, arranged in bilaterally symmetric fashion as a stack of \(2n\) rows of squares, the rows having lengths \(2,4,6,\dots, 2n-2\), \(2n\), \(2n\), \(2n-2,\dots,6,4,2\). N. Elkies, G. Kuperberg, M. Larsen and J. Propp [J. Algebr. Comb. 1, No. 2, 111-132 (1992; Zbl 0779.05009)] showed that an Aztec diamond of order \(n\) can be tiled by dominoes in exactly \(2^{n(n+ 1)/2}\) ways. Here the authors pay particular attention to the line that separates the NW and the SE half of the Aztec diamond (the spine) or rather the \(2k= 2\left\lceil{n\over 2}\right\rceil\) squares that cover it. In any tiling, \(k\) of these squares belong to tiles that lie mainly in the NW half, the other \(k\) belong to tiles that lie mainly in the SE half. Prescribing for each of the \(k\) even-numbered squares whether it should belong to a tile that belongs mainly to the NW or to the SE (putting barriers toward the SE, or to the NW, resp.) is compatible with \(2^{n(n+ 1)/2}/2^k\) tilings, irrespective of the prescription. The problem can be restated in terms of determinants, and is solved using the Jakobi-Trudi identity.

Reviewer: J.Schaer (Calgary)

MSC:

05B45	Combinatorial aspects of tessellation and tiling problems
52C20	Tilings in \(2\) dimensions (aspects of discrete geometry)

Keywords:

domino tiling; Aztec diamond

Citations:

Zbl 0779.05009

References:

[1]	Elkies, N.; Kuperberg, G.; Larsen, M.; Propp, J., Alternating sign matrices and domino tilings, part 1, J. Algebraic Combin., 1, 111-132 (1992) · Zbl 0779.05009
[2]	Elkies, N.; Kuperberg, G.; Larsen, M.; Propp, J., Alternating sign matrices and domino tilings, part 2, J. Algebraic Combin., 1, 219-234 (1992) · Zbl 0788.05017
[3]	Fulmek, M., A Schur function identity, J. Combin. Theory Ser. A, 77, 177-180 (1997) · Zbl 0865.05076
[4]	Macdonald, I. G., Symmetric Functions and Hall Polynomials (1979), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0487.20007
[5]	Mills, W. H.; Robbins, D. P.; Rumsey, H., Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A, 34, 340-359 (1983) · Zbl 0516.05016
[6]	Sagan, B. E., The Symmetric Group (1991), Wadsworth and Brooks/Cole: Wadsworth and Brooks/Cole Pacific Grove · Zbl 0823.05061
[7]	Stanley, R., Theory and application of plane partitions, Parts 1 and 2, Stud. Appl. Math., 50, 167-188 (1971) · Zbl 0225.05011
[8]	Stanley, R., Enumerative Combinatorics (1999), Cambridge Univ. Press: Cambridge Univ. Press New York/Cambridge · Zbl 0928.05001
[9]	Turnbull, H. W., The Theory of Determinants, Matrices, and Invariants (1929), Blackie: Blackie London/Glasgow · Zbl 0103.00702