Counting domino tilings of rectangles via resultants. (English) Zbl 0994.05051

Strehl, Volker

Adv. Appl. Math. 27, No. 2-3, 597-626 (2001).

The “cosine formula” discovered independently in 1961 by P. W. Kasteleyn and by the reviewer and M. Fisher [Philos. Mag., VIII. Ser. 6, 1061-1063 (1961; Zbl 0126.25102)] for the number of domino tilings of a rectangle is related to other combinatorial results such as the enumeration of domino “heaps” which are also related to Chebyshev polynomials (which enumerate Dyck or Motzkin paths on a certain lattice) and pairs of complementary path systems are related to systems of trivial heaps by a determinantal product described as the resultant.
No proofs of the many results and relationships quoted are given but are “illustrated” by a typical example, or the literature is referred to.

Reviewer: H.N.V.Temperley (Langport)

MSC:

05B45

Combinatorial aspects of tessellation and tiling problems

Keywords:

domino tilings; enumeration; resultant

Citations:

Zbl 0126.25102

References:

[1]	Andrews, G. E., The Rogers-Ramanujan reciprocal and Minc’s partition function, Pacific J. Math., 95, 251-256 (1981) · Zbl 0514.10007
[2]	Cartier, P.; Foata, D., Problèmes combinatoires de commutation et réarrangements (1969), Springer-Verlag: Springer-Verlag Berlin · Zbl 0186.30101
[3]	Chow, T. Y., Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function, J. Algebraic Combin., 10, 227-240 (1999) · Zbl 0944.05095
[4]	Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[5]	Carlitz, L.; Scoville, R.; Vaughan, T., Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math., 19, 211-243 (1976) · Zbl 0348.05006
[6]	Diekert, V., Combinatorics on traces (1990), Springer-Verlag: Springer-Verlag Berlin · Zbl 0717.68002
[7]	Diekert, V.; Métivier, Y., Partial commutation and traces, Handbook of Formal Languages (1997), Springer-Verlag: Springer-Verlag Berlin, p. 457-533
[8]	Gronau, H.-D. O.F.; Just, W.; Schade, W.; Scheffler, P.; Wojciechowski, J., Path systems in acyclic directed graphs, Zastos. Mat., 19, 399-411 (1988) · Zbl 0718.05031
[9]	Gessel, I. M.; Viennot, G. X., Binomial determinants, paths, and hook length formulae, Adv. in Math., 58, 300-321 (1985) · Zbl 0579.05004
[10]	I. M. Gessel, and, G. X. Viennot, Determinant, paths, and plane partitions, preprint, 2000, http://www.cs.brandeis.edu/vira; I. M. Gessel, and, G. X. Viennot, Determinant, paths, and plane partitions, preprint, 2000, http://www.cs.brandeis.edu/vira
[11]	John, P. E.; Sachs, H., On a strange observation in the theory of the dimer problem, Discrete Math., 216, 211-219 (2000) · Zbl 0955.05078
[12]	John, P.; Sachs, H.; Zernitz, H., Problem 5. Domino covers in square chessboards, Zastos. Mat., 19, 635-641 (1988)
[13]	Kasteleyn, P. W., The statistics of dimers on a lattice, Physica, 27, 1209-1225 (1961) · Zbl 1244.82014
[14]	C. Krattenthaler, Permutations with restricted patterns and Dyck paths, preprint.; C. Krattenthaler, Permutations with restricted patterns and Dyck paths, preprint. · Zbl 0994.05001
[15]	Krattenthaler, C., Generating functions for plane partitions of a given shape, Manuscripta Math., 69, 173-201 (1990) · Zbl 0726.05007
[16]	Lieb, E. H., Solution of the dimer problem by the transfer matrix method, J. Math. Phys., 8, 2339-2341 (1967)
[17]	Lindström, B., On the vector representations of induced matroids, Bull. London Math. Soc., 5, 85-90 (1973) · Zbl 0262.05018
[18]	Lovász, L., Combinatorial Problems and Exercises (1979), North-Holland: North-Holland Amsterdam · Zbl 0439.05001
[19]	Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[20]	Montroll, E. W., Lattice statistics, (Beckenbach, E. F., Applied Combinatorial Mathematics (1964), Wiley: Wiley New York/London/Sydney), 96-143 · Zbl 0141.15503
[21]	Pachter, L., Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electron. J. Combin., 4, Rp 29 (1997) · Zbl 0886.05046
[22]	Paule, P., Short and easy computer proofs of the Rogers-Ramanujan identities and of identities of similar type, Electron. J. Combin., 1, 10 (1994) · Zbl 0814.05009
[23]	Percus, J. K., Combinatorial Methods (1971), Springer-Verlag: Springer-Verlag New York · Zbl 0268.05003
[24]	Propp, J., Enumeration of matchings: problems and progress, New Perspectives in Algebraic Combinatorics, Berkeley, CA, 1996-97 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, p. 255-291 · Zbl 0937.05065
[25]	Rivlin, T. J., Chebyshev Polynomials (1990), Wiley: Wiley New York · Zbl 0734.41029
[26]	Stanley, R. P., On dimer coverings of rectangles of fixed width, Discrete Appl. Math., 12, 81-87 (1985) · Zbl 0617.05021
[27]	Stanley, R. P., Enumerative Combinatorics (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
[28]	Sundquist, T. S.; Wagner, D. G.; West, J., A Robinson-Schensted algorithm for a class of partial orders, J. Combin. Theory Ser. A, 79, 36-52 (1997) · Zbl 0882.05113
[29]	Sachs, H.; Zernitz, H., Remark on the dimer problem, Discrete Appl. Math., 51, 171-179 (1994) · Zbl 0808.05034
[30]	Temperley, H. N.V.; Fisher, M. E., Dimer problem in statistical mechanics—an exact result, Philos. Mag. (8), 6, 1061-1063 (1961) · Zbl 0126.25102
[31]	Viennot, G. X., Heaps of pieces. I. Basic definitions and combinatorial lemmas, Combinatoire énumérative, Montreal, Que., 1985/Quebec, Que., 1985 (1986), Springer-Verlag: Springer-Verlag Berlin, p. 321-350 · Zbl 0618.05008
[32]	Viennot, G. X., Bijections for the Rogers-Ramanujan reciprocal, J. Indian Math. Soc. (N.S.), 52, 171-183 (1988) · Zbl 0664.05005