TOPICS
Search

Rook Number


The rook numbers r_k^((m,n)) of an m×n board are the number of subsets of size k such that no two elements have the same first or second coordinate. In other word, it is the number of ways of placing k rooks on a board such that none attack each other (one form of the so-called rooks problem). The rook number r_k is therefore the leading coefficient of the corresponding rook polynomial R_(mn)(x).

For an n×n board, each n×n permutation matrix corresponds to an allowed configuration of rooks. However, the permutation matrices give only a subset of the total number of solutions, which on an n×n board is simply the factorial n!. This can be seen easily by noting that there are n ways to place the first rook in the first column, n-1 ways to place the second rook in the second column, n-2 ways to place the third rook, ..., and a single way to place the nth rook in the last (nth) column.

The rook numbers of a board determine the rook numbers of the complementary board B^_, written as d×d\B. This is known as the rook reciprocity theorem.


See also

Permutation Matrix, Rook Polynomial, Rook Reciprocity Theorem, Rooks Problem

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Rook Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RookNumber.html

Subject classifications