Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: A reciprocity theorem for domino tilings. | A reciprocity theorem for domino tilings James Propp Department of Mathematics University of Wisconsin - Madison Wisconsin USA propp@math.wisc.edu Submitted April 1 2001 Accepted April 30 2001 MR Subject Classifications 05A15 52C20 Abstract Let T m n denote the number of ways to tile an m-by-n rectangle with dominos. For any fixed m the numbers T m n satisfy a linear recurrence relation and so may be extrapolated to negative values of n these extrapolated values satisfy the relation T m 2 n em nT m n where m n 1 if m 2 mod 4 and n is odd and where Em n 1 otherwise. This is equivalent to a fact demonstrated by Stanley using algebraic methods. Here I give a proof that provides among other things a uniform combinatorial interpretation of T m n that applies regardless of the sign of n. 1 Introduction It has undoubtedly been observed many times that the Fibonacci sequence when run backwards as well as forwards from its initial conditions yields a doubly-infinite sequence that is symmetrical modulo some minus-signs 8 5 3 2 110 11 2 35 8 We will see that this is just one instance of a more general phenomenon involving domino tilings of rectangles. For positive integers m and n let T m n denote the number of ways to cover an m-by-n rectangle with 1-by-2 rectangles dominos with pairwise disjoint interiors. When m 2 the values T m n form the Fibonacci sequence more generally for each fixed m the values of T m n form a sequence satisfying a higher-order linear recurrence relation see section 4 for an explanation of why such a recurrence relation must exist . These recurrences allow one to extrapolate T m n to negative values of n in a natural way for each fixed positive integer m. There are in fact infinitely many recurrences one could Supported by grants from the National Science Foundation and the National Security Agency. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R18 1 employ but as section 4 explains the extrapolated values of T m n do not depend on which of the .
