tailieunhanh - Báo cáo toán học: "Counting Fixed-Height Tatami Tilings"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Counting Fixed-Height Tatami Tilings. | Counting Fixed-Height Tatami Tilings Frank Ruskey Department of Computer Science University of Victoria PO BOX 3055 Victoria BC Canada V8W 3P6 ruskey@ Jennifer Woodcock Department of Computer Science University of Victoria PO BOX 3055 Victoria BC Canada V8W 3P6 jwoodcoc@ Submitted Jul 10 2009 Accepted Sep 30 2009 Published Oct 12 2009 Mathematics Subject Classification 05B45 05A19 Abstract A tatami tiling is an arrangement of 1 X 2 dominoes or mats in a rectangle with m rows and n columns subject to the constraint that no four corners meet at a point. For fixed m we present and expand upon Dean Hickerson s combinatorial decomposition of the set of tatami tilings a decomposition that allows them to be viewed as certain classes of restricted compositions when n m. Using this decomposition we find the ordinary generating functions of both unrestricted and inequivalent tatami tilings that fit in a rectangle with m rows and n columns for fixed m and n m. This allows us to verify a modified version of a conjecture of Knuth. Finally we give explicit solutions for the count of tatami tilings in the form of sums of binomial coefficients. 1 Introduction In the dimer problem one wishes to count the number of different dimer configurations -ways to cover an m by n rectangle by 1 by 2 tiles. An equivalent problem is counting the number of perfect matchings in a grid graph. Many papers have been written about the Research supported in part by Natural Sciences and Engineering Research Council of Canada NSERC Discovery and Equipment grants. Research supported by an NSERC PGS-D scholarship. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R126 1 Figure 1 Some forbidden configurations for tatami tilings Figure 2 Typical tatami tilings for m 2 3 4. dimer problem and its variants. See for example Read 5 or Section The Dimer Problem and Perfect Matchings of Aigner 1 . Dimer configurations are also sometimes called domino tilings and we will use the word tiling .