The set (§26.13) can be identified with the set of matrices of 0’s and 1’s with exactly one 1 in each row and column. The permutation corresponds to the matrix in which there is a 1 at the intersection of row with column , and 0’s in all other positions. The permutation corresponds to the matrix
The sign of the permutation is the sign of the determinant of its matrix representation. The inversion number of is a sum of products of pairs of entries in the matrix representation of :
where the sum is over and .
The matrix represents the placement of nonattacking rooks on an chessboard, that is, rooks that share neither a row nor a column with any other rook. A permutation with restricted position specifies a subset . If , then . The number of derangements of is the number of permutations with forbidden positions .
Let be the number of ways of placing nonattacking rooks on the squares of . Define . For the problem of derangements, . The rook polynomial is the generating function for :
If , where no element of is in the same row or column as any element of , then
For , denotes after removal of all elements of the form or , . denotes with the element removed.
is the number of permutations in for which exactly of the pairs are elements of . is the generating function:
The number of permutations that avoid is
The problème des ménages asks for the number of ways of seating married couples around a circular table with labeled seats so that no men are adjacent, no women are adjacent, and no husband and wife are adjacent. There are ways to place the wives. Let . Then
The solution is
The Ferrers board of shape , , is the set . For this set,
If is the Ferrers board of shape , then
and therefore by (26.8.10),