Đ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 ngành toán học tạp chí toán học quốc tế đề tài: A Short Proof of the Rook Reciprocity. | A Short Proof of the Rook Reciprocity Theorem Timothy Chow Dept. of Mathematics Univ. of Michigan Ann Arbor MI 48109 U.S.A. email tchow@umich.edu Submitted February 12 1996 Accepted March 4 1996. Abstract. Rook numbers of complementary boards are related by a reciprocity law. A complicated formula for this law has been known for about fifty years but recently Gessel and the present author independently obtained a much more elegant formula as a corollary of more general reciprocity theorems. Here following a suggestion of Goldman we provide a direct combinatorial proof of this new formula. MR primary subject number 05A19 MR secondary subject numbers 05A05 05A15 A board B is a subset of d d where d is defined to be 1 2 . dg and the rook numbers rg of a board are the number of subsets of B of size k such that no two elements have the same first coordinate or the same second coordinate i.e. the number of ways of placing k non-taking rooks on B . It has long been known 5 that the rook numbers of a board B determine the rook numbers of the complementary board B defined to be d X d B according to the polynomial identity d d X rg d k xk X 1 k rg d k xk x i d k. k 0 k 0 Recently a simpler formulation of this identity was found independently by Gessel 2 and Chow 1 . To state it we follow 4 in defining d R B x d f X rgx k 0 where xn d f x x 1 x 2 x n 1 . Then we have the following reciprocity theorem. Theorem. For any board B c d X d R B x 1 dR B x 1 . The existing proofs derive this as a corollary of other reciprocity theorems but Goldman 3 has suggested that a direct combinatorial proof ought to be possible. Indeed it 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R 10 2 is and the purpose of this note is to provide such a proof. The knowledgeable reader will recognize that the main idea is borrowed from 4 . Proof. Observe that d -1 dR B - x - 1 1 d X rB - x - M k 0 d X - 1 krB x d - k -. k 0 First assume x is a positive integer. Add x extra rows to d X d . Then rB x d -
