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.
Definition
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\]
One day, a particular family went to a restaurant to have their Christmas dinner. This family has children, Adam, Ben, Carrie and David who are choosy over their food. Luckily, the restaurant provides set meals specifically made for choosy children, namely, Chicken Burger, Vegetable Frenzy, Spicy Gala and Steak.
Adam doesn't eat chicken and vegetable; Ben doesn't eat spicy food; Carrie doesn't eat chicken; and David doesn't eat beef. In how many ways can Mum order for a different set meal for each of the children such that all end up satisfied? (The children don't want to be called "copycats" so they all want different set meals from each other.)