Editing Inclusion–exclusion principle (section)

===Rook polynomials===
{{main|Rook polynomial}}

A rook polynomial is the [[generating polynomial|generating function]] of the number of ways to place non-attacking [[rook (chess)|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<sub>k</sub>''(''B'') of ''x<sup>k</sup>'' in the rook polynomial ''R<sub>B</sub>''(''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 <math>B'</math> consisting of the squares of the rectangular board that are not in ''B''. This complementary board also has a rook polynomial <math>R_{B'}(x)</math> with coefficients <math>r_k(B').</math>

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<sub>n</sub>''(''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]]:

:<math>(m)_n = m(m-1)(m-2) \cdots (m-n+1).</math>

Letting ''P''<sub>i</sub> 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:<ref>{{harvnb|Roberts|Tesman|2009|loc=pp.419–20}}</ref>

:<math> r_n(B) = \sum_{t=0}^n (-1)^t (m-t)_{n-t} r_t(B'). </math>