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 such that none attack each other. The rook numbers of a board determine the rook numbers of the complementary board , defined to be . 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 board, each 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.