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, …, d}) and the rook numbers r_{k}^{B} 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 \overline{B} (defined to be ([d] × [d])\B) according to the polynomial identity

∑_{k=0}^{d} r_{k}^{B}(d − k)! x^{k} = ∑_{k=0}^{d}(−1)^{k}r\overline{B} ; k(d − k)! x^{k}(x + 1)^{d−k}.

Recently, a simpler formulation of this identity was found independently by Gessel [2] and Chow [1]. To state it, we follow [4] in defining

R(B; x) =^{def} ∑_{k=0}^{d} r_{k}^{B}x\underline{d−k},

where x\underline{n} =^{def} x(x−1)(x−2) ⋯ (x−n+1). Then we have the following reciprocity theorem.

Theorem. For any board B ⊂ [d] × [d],

R(\overline{B}; x) = (−1)^{d}R(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 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

\begin{aligned}(−1)^{d}R(B; − x − 1) & = (−1)^{d} ∑_{k=0}^{d} r_{k}^{B}( − x − 1)\underline{d−k} \\ & = ∑_{k=0}^{d}(−1)^{k}r_{k}^{B}(x + d − k)\underline{d−k}. \end{aligned}

First assume x is a positive integer. Add x extra rows to [d] × [d]. Then r_{k}^{B}(x + d − k)\underline{d−k} is the number of ways of first placing k rooks on B and then placing d − k more rooks anywhere (i.e., on B, \overline{B} or on the extra rows) such that no two rooks can take each other in the final configuration. By inclusion-exclusion, we see that the resulting configurations in which the set S of rooks on B is nonempty cancel out of the above sum, because they are counted once for each subset of S, with alternating signs. Thus what survives is the set of placements of d non-taking rooks on the extended board such that no rook lies on B. But it is clear that this is precisely what R(\overline{B}; x) enumerates. Therefore the theorem holds for all positive integers x and since it is a polynomial equation it holds for all x.

Acknowledgments

This work was supported in part by a National Science Foundation Graduate Fellowship and a National Science Foundation Postdoctoral Fellowship.

References

[1] T. Chow, The path-cycle symmetric function of a digraph, Advances in Math., in press.

[2] I. M. Gessel, personal communication.

[3] J. R. Goldman, personal communication.

[4] J. R. Goldman, J. T. Joichi, and D. E. White, Rook theory I. Rook equivalence of Ferrers boards, Proc. Amer. Math. Soc. 52 (1975), 485–492.

[5] J. Riordan, “An Introduction to Combinatorial Analysis,” Wiley, New York, 1958.