Rook Polynomial

The rook polynomial is the generating function for the numbers of arrangement of $k$ non-attacking rooks on a board $B$. For those who are new to chess, rooks are chess piece that move and attack horizontally and vertically. Hence, for rooks to be non-attacking to each other, they must not be placed on the same row or column of the board.

In general, the rook polynomial of a $m \times n$ board $B_{m,n}$ (denoted as $R(x, B_{m,n})$) is $$R(x,B_{m,n}) = \displaystyle \sum_{k=0}^\infty r_k(B_{m,n})x^k,$$ where, $r_k$ is the number of ways to arrange $k$ non-attacking rooks on board $B_{m,n}$. For example $R(x, B_{1,1}) = x +1$ since there are $1$ way (coefficient of $x^0 = 1$) to place $0$ non-attacking rook and $1$ way (coefficient of $x^1$) to place $1$ non-attacking rook.

So, how do we deduce a generalization for the rook's polynomial for $2$-dimensional board $B_{m,n}$?

Letting $i = \min \{m,n\},$ we get $$R(x,B_{m,n}) = \displaystyle \sum_{k=0}^i \binom{m}{k} P(n,k) \text{ } x^k.$$

The above can be derived by first choosing $k$ rows out of the board's $m$ rows; then permutating the $k$ out of the $n$ columns (denoted by $P(n,k)$). Recall that $k$ refers to the numbers of non-attacking rooks placed on the board.

One way we can apply the rook's polynomial to combinatorics question is by labelling values/variables to the rows and columns of the board.

David, Mark, Jerry and Kai joined a card game club. They are required to choose 1 out of the 5 card games available in the club ---- namely, Monopoly Deal, Poker, Blackjacks, Uno and Cheat. How many ways are there for each of David, Mark, Jerry and Kai to choose a different card game from each other?

---

Label the rows of board $B_{4 \times 5}$ with the names (David, Mark, Jerry and Kai), and the columns with the card games (Monopoly Deal, Poker, Blackjacks, Uno and Cheat). Since each of the members must choose only $1$ card game and each card game can only be chosen by at most $1$ member, we can use the rook polynomial to find the ways to arrange $4$ non-attacking rooks on board $B_{4 \times 5}$. The answer to the question is hence

$$\binom{4}{4} P(5,4) = 120.\ _\square$$