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.