tailieunhanh - Báo cáo toán học: " Enumeration of Tilings of Diamonds and Hexagons with Defects"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Enumeration of Tilings of Diamonds and Hexagons with Defects. | Enumeration of Tilings of Diamonds and Hexagons with Defects Harald A. Helfgott Department of Mathematics Princeton University Princeton NJ 08544 haraldh@ Ira M. Gessel Mathematics Department Brandeis University Waltham MA 02254-9110 gessel@ Submitted August 1 1998 Accepted February 23 1999 Classification 05B40 05C70 Abstract We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular we obtain solutions to open problems 1 2 and 10 in James Propp s list of problems on enumeration of matchings 22 . 1. Introduction While studying dimer models P. W. Kasteleyn 15 noticed that tilings of very simple figures by very simple tiles can be not only plausible physical models but also starting points for some very interesting enumeration problems. Kasteleyn himself solved the problem of counting tilings of a rectangle by dominoes. He also found a general method now known as Kasteleyn matrices for computing the number of tilings of any bipartite planar graph in polynomial time. Kasteleyn s method has proven very useful for computational-experimental work but it does not of itself provide proofs of closed formulas for specific enumeration problems. We shall see a few examples of problems for which Kasteleyn matrices alone are inadequate. By an a b C d e f hexagon we mean a hexagon with sides of lengths a b C d e f and angles of 120 degrees subdivided into equilateral triangles of unit side by lines parallel to the sides. We draw such a hexagon with the sides of lengths a b C d e f in clockwise order so that the side of length b is at the top and the side of length e is at the bottom. We shall use the term a b C hexagon for an a b C a b C hexagon. Thus Figure 2 shows a 3 4 3 hexagon. THE ELECTRONIC JOURNAL OF COMBINATORICS 6 1999 R16 2 Figure 1. Aztec diamond of order 3 Figure 2. 3 4 3 hexagon An Aztec diamond of order n is the .