Rook Polynomials and Non-Attacking Rooks

A rook attacks every cell in its own row and column, so a set of rooks is non-attacking when no two share a row or a column. Given a board $B$ — a chosen set of allowed cells inside an $m\times n$ grid (the other cells are forbidden) — we want to count placements of $k$ non-attacking rooks that use only allowed cells.

Definition

Let $r_k(B)$ be the number of ways to place $k$ non-attacking rooks on the allowed cells of $B$. The rook polynomial of $B$ packages all of these counts into one generating function:

$R_B(x)=\sum_{k\ge 0} r_k(B)\,x^{k}=r_0 + r_1 x + r_2 x^{2}+\cdots$

Here $r_0=1$ (the empty placement) and $r_1$ is just the number of allowed cells. The polynomial stops at the largest $k$ for which a placement exists, so $\deg R_B \le \min(m,n)$.

Two facts that crack most konkur problems

1. Top coefficient = permanent. On a square $n\times n$ board, placing $n$ non-attacking rooks forces exactly one rook per row and per column, i.e. a permutation $\sigma\in S_n$ with every cell $(i,\sigma(i))$ allowed. So the coefficient of $x^{n}$ is

$r_n(B)=\operatorname{per}(M),\qquad M_{ij}=\begin{cases}1 & (i,j)\text{ allowed}\\ 0 & \text{forbidden,}\end{cases}$

the permanent of the $0/1$ allowed-cell matrix (the determinant formula but with all $+$ signs).

2. Product rule for blocks. If the allowed cells split into two sub-boards that share no row and no column (disjoint blocks $B_1,B_2$), then

$R_{B_1\cup B_2}(x)=R_{B_1}(x)\cdot R_{B_2}(x).$

This lets you factor a scattered board into tiny independent pieces and multiply their polynomials.

How to apply it

Two complementary routes, depending on whether allowed or forbidden cells are sparser:

For the inclusion–exclusion route on an $n\times n$ board with forbidden set $F$, the number of full permutations avoiding all forbidden cells is

$r_n = \sum_{j\ge 0}(-1)^{j}\,r_j(F)\,(n-j)!,$

where $r_j(F)$ counts $j$ non-attacking rooks placed on the forbidden cells — exactly the coefficients of the rook polynomial of the forbidden board $F$.

Mini-example

Take a $3\times 3$ board with the three diagonal cells $(1,1),(2,2),(3,3)$ forbidden (allowed = everything off the diagonal). The number of ways to place $3$ non-attacking rooks is the count of $\sigma\in S_3$ with $\sigma(i)\ne i$ for all $i$ — the derangements $D_3=2$.

Check it with inclusion–exclusion. The forbidden diagonal is itself non-attacking, so $r_j(F)=\binom{3}{j}$, giving

$r_3=\sum_{j=0}^{3}(-1)^{j}\binom{3}{j}(3-j)! = 6 - 3\cdot 2 + 3\cdot 1 - 1 = 2.\ \checkmark$

(This is why counting permutations that dodge forbidden squares — the rook-polynomial problem — generalizes the derangement count.)

Exam trick: the coefficient of $x^{n}$ in the rook polynomial of an $n\times n$ board is just the permanent of its allowed-cell matrix = the number of allowed full permutations. You never need the lower coefficients — when forbidden cells are few, count directly with $r_n=\sum_j(-1)^j r_j(F)(n-j)!$ over the forbidden board, not the whole grid.