Rook Number

The rook numbers $r_n^B$ of an $n\times n$ Board $B$ are the number of subsets of size $n$ such that no two elements have the same first or second coordinate. In other word, it is the number of ways of placing $n$ rooks on $B$ such that none attack each other. The rook numbers of a board determine the rook numbers of the complementary board $\overline{B}$, defined to be ${\bf d}\times{\bf d}\backslash B$. This is known as the Rook Reciprocity Theorem. The first few rook numbers are 1, 2, 7, 23, 115, 694, 5282, 46066, ... (Sloane's A000903). For an $n\times n$ board, each $n\times n$ Permutation Matrix corresponds to an allowed configuration of rooks.

See also Rook Reciprocity Theorem

References

Sloane, N. J. A. Sequence A000903/M1761 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.