The rook numbers
of an
board
are the number of subsets of size
such that no two elements have the same first or second coordinate.
In other word, it is the number of ways of placing
rooks on a board such that none attack each other (one form
of the so-called rooks problem). The rook number
is therefore the leading coefficient
of the corresponding rook polynomial
.
For an
board, each
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
board is simply the factorial
. This can be seen easily by noting that there are
ways to place the first rook in the first column,
ways to place the second rook in the second column,
ways to place the third rook, ...,
and a single way to place the
th rook in the last (
th) column.
The rook numbers of a board determine the rook numbers of the complementary board , written as
. This is known as the rook
reciprocity theorem.