Hello! After reading so many useful posts on Brilliant, I have finally set my mind to do one (my first!) on Rook's Polynomial, a useful technique for many combinatorics question (those with certain restrictions as you will see below).
To elaborate further on what exactly is the Rook's Polynomial, it is the generating function for the numbers of arrangement of non-attacking rooks on a board . 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 board (denoted as ) is:
where, is the number of ways to arrange non attacking rooks on board . For example since there are way (coefficient of ) to place non-attacking rook and way (coefficient of ) to place non-attacking rook.
So, how do we deduce a generalisation for the Rook's polynomial for -Dimensional board ? Letting , we get
The above can be derived by first choosing rows out of the board's rows; then permutating the out of the columns (denoted by ). Recall that 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. A simple example question is as follows:
Solution: Label the rows of board 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 card game and each card game can only be chosen by at most member, we can use the rook polynomial to find the ways to arranging non-attacking rooks on board . The answer to the question is hence,
Rook's Polynomial is a really interesting and (for me) quite a rare topic. Hope you have enjoyed and learnt something! Since there are much more about Rook's Polynomial, you can read it up here! :) Thanks!
Image from: Google Search (chess.com)