An introduction to Rook's Polynomial (Combinatorics)

This note has been used to help create the Rook Polynomial wiki

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 kk non-attacking rooks on a board BB. 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×nm \times n board Bm,nB_{m,n} (denoted as R(x,Bm,n)R(x, B_{m,n})) is: R(x,Bm,n)=k=0rk(Bm,n)xkR(x,B_{m,n}) = \displaystyle \sum_{k=0}^\infty r_k(B_{m,n})x^k

where, rkr_k is the number of ways to arrange kk non attacking rooks on board Bm,nB_{m,n}. For example R(x,B1,1)=x+1 R(x, B_{1,1}) = x +1 since there are 11 way (coefficient of x0=1x^0 = 1) to place 00 non-attacking rook and 11 way (coefficient of x1x^1) to place 11 non-attacking rook.

So, how do we deduce a generalisation for the Rook's polynomial for 22 -Dimensional board Bm,nB_{m,n}? Letting i=min{m,n}i = \min \{m,n\}, we get R(x,Bm,n)=k=0i(mk)P(n,k) xkR(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 kk rows out of the board's mm rows; then permutating the kk out of the nn columns (denoted by P(n,k)P(n,k)). Recall that kk 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:

  1. David, Mark, Jerry and Kai joined a card game club. They are required to choose 11 out of the 55 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?

Solution: Label the rows of board B4×5B_{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 11 card game and each card game can only be chosen by at most 11 member, we can use the rook polynomial to find the ways to arranging 44 non-attacking rooks on board B4×5B_{4 \times 5}. The answer to the question is hence, (44)P(5,4)=120\binom{4}{4} P(5,4) = 120

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!

  • After you have read the above link: You can try this problem which can be solved by Rook's Polynomial.

Image from: Google Search (chess.com)

Note by Happy Melodies
5 years, 6 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Wow, I have never heard of this concept before. Thank you for sharing, very nice first post!

Daniel Liu - 5 years, 6 months ago

Log in to reply

Thanks for the encouragement :) have just read about it not long ago too

Happy Melodies - 5 years, 6 months ago

Log in to reply

Really brilliant, I've never seen such a good way of translating such ugly combinatorics questions into something with a fairly nice solution

Josh Rowley - 5 years, 6 months ago

Log in to reply

Nice explanation :) Thanks for the sample problems too!

Sherry Sarkar - 5 years, 6 months ago

Log in to reply

Thanks! :) the link above has more details and sample questions for you to explore!

Happy Melodies - 5 years, 6 months ago

Log in to reply

Superb.

Soham Dibyachintan - 5 years, 6 months ago

Log in to reply

Very nice first post!

Eddie The Head - 5 years, 6 months ago

Log in to reply

Thanks!

Happy Melodies - 5 years, 6 months ago

Log in to reply

The link is also very informative....totally worth checking out

Eddie The Head - 5 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...