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 . email tchow@ 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 . 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 -
