linguistic:translation, information:filtering, stylistic:style_transfer, linguistic:voice_change
Rook polynomials

A rook polynomial is the generating function of the number of ways to place non-attacking rooks on a board B that looks like a subset of the squares of a checkerboard; that is, no two rooks may be in the same row or column. The board B is any subset of the squares of a rectangular board with n rows and m columns; we think of it as the squares in which one is allowed to put a rook. The coefficient, r (B) of x in the rook polynomial R (x) is the number of ways k rooks, none of which attacks another, can be arranged in the squares of B. For any board B, there is a complementary board B ′ {\displaystyle B'} consisting of the squares of the rectangular board that are not in B. This complementary board also has a rook polynomial R B ′ (x) {\displaystyle R_{B'}(x)} with coefficients r k (B ′). {\displaystyle r_{k}(B').}

It is sometimes convenient to be able to calculate the highest coefficient of a rook polynomial in terms of the coefficients of the rook polynomial of the complementary board. Without loss of generality we can assume that n ≤ m, so this coefficient is r (B). The number of ways to place n non-attacking rooks on the complete n × m "checkerboard" (without regard as to whether the rooks are placed in the squares of the board B) is given by the falling factorial:

Letting P be the property that an assignment of n non-attacking rooks on the complete board has a rook in column i which is not in a square of the board B, then by the principle of inclusion–exclusion we have: