A Generator of Rook Polynomials

General

On a chessboard of any configuration, a rook is *nontaking* if the cell it occupies is not in the same row or column as the cell of any other rook. A *rook polynomial* is an ordinary generating function in which the coefficient of () is the number of ways *k *nontaking rooks can be distributed on a finite board. Rook polynomials have many applications in combinatorics, especially in counting restricted permutations. A chessboard can be described mathematically as an ordered set of its cells' unique (row, column) pairs. A chessboard need not be rectangular. The algorithm for finding rook polynomials discussed in this article is an adaptation of a well-known inclusion-exclusion method, typically described by Riordan [1, 168-170] and Liu [2, 111-118].

This method selects any cell of the board as a *special cell*. As Liu observes, the number of ways *k *nontaking rooks on the original chessboard is the number of ways with a rook always *included* in the special cell plus the number of ways with all rooks *excluded* from the special cell. The board is found by crossing out the row *and* column of the special cell. The contribution of the rook polynomial from must be multiplied by *x* to account for the loss of the cell along with its row and column. The board is found by eliminating the special cell completely. Hence, forms an interesting "equation " in *x*, with chessboards as coefficients. Continued reductions of and and their successor boards yield nested sets of *x'*s from which the rook polynomial of board *C* emerges. When working "by hand, " recognition of the rook polynomials of intermediate boards often shortens this search--a luxury usually not afforded in a computer reduction.