Timothy Chow Dept of Mathematics Univ of Michigan Ann Arbor MI 48109 U S A email

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] \Theta [d] (where [d] is defined to be f1; 2; : : : ; dg) and the rook numbers r B k 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] \Theta [d])nB) according to the polynomial identity d X k=0 r B k ...