how to generate rook polynomial

Question

I've encountered rook polynomials. I just can't seem to understand how to generate them by hand for small examples such as 3x3 boards.

Take for instance:

$$\begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ \end{matrix}$$

where $0$ means occupied.

I'd appreciate a guide or at least a suitable literature, where it's explained. Thanks.

Answer 1

For the board that's given, the rook polynomial would be $R(x)=1+6x+7x^2+x^3$,

since the coefficient of $x^n$ is the number of ways to place n non-attacking rooks on the board.

---

In addition to direct counting, the rook polynomial can be found by selecting a specific position, such as the third 1 in row 2, and using that

the rook polynomial with this place deleted is $r_1(x)=1+5x+4x^2$, and

the rook polynomial with this row and column deleted is $r_2(x)=1+3x+x^2$;

so the rook polynomial for the board is given by

$R(x)=r_1(x)+xr_2(x)=1+5x+4x^2+x(1+3x+x^2)=1+6x+7x^2+x^3$.

---

A good reference for this topic is Alan Tucker's "Applied Combinatorics".