§26.15 Permutations: Matrix Notation

The set ${𝔖}_n$ (§26.13) can be identified with the set of $n\times n$ matrices of 0’s and 1’s with exactly one 1 in each row and column. The permutation $\sigma$ corresponds to the matrix in which there is a 1 at the intersection of row $j$ with column $\sigma (j)$, and 0’s in all other positions. The permutation $35247816$ corresponds to the matrix

The sign of the permutation $\sigma$ is the sign of the determinant of its matrix representation. The inversion number of $\sigma$ is a sum of products of pairs of entries in the matrix representation of $\sigma$:

where the sum is over and $n\ge h>\mathrm{\ell }\ge 1$.

The matrix represents the placement of $n$ nonattacking rooks on an $n\times n$ chessboard, that is, rooks that share neither a row nor a column with any other rook. A permutation with restricted position specifies a subset $B\subseteq \{1,2,\mathrm{\dots },n\}\times \{1,2,\mathrm{\dots },n\}$. If $(j,k)\in B$, then $\sigma (j)\ne k$. The number of derangements of $n$ is the number of permutations with forbidden positions $B=\{(1,1),(2,2),\mathrm{\dots },(n,n)\}$.

Let $r_j(B)$ be the number of ways of placing $j$ nonattacking rooks on the squares of $B$. Define $r_0(B)=1$. For the problem of derangements, $r_j(B)=\left(\genfrac{}{}{0.0pt}{}{n}{j}\right)$. The rook polynomial is the generating function for $r_j(B)$:

If $B=B_1\cup B_2$, where no element of $B_1$ is in the same row or column as any element of $B_2$, then

For $(j,k)\in B$, $B\setminus [j,k]$ denotes $B$ after removal of all elements of the form $(j,t)$ or $(t,k)$, $t=1,2,\mathrm{\dots },n$. $B\setminus (j,k)$ denotes $B$ with the element $(j,k)$ removed.

$N_k(B)$ is the number of permutations in ${𝔖}_n$ for which exactly $k$ of the pairs $(j,\sigma (j))$ are elements of $B$. $N(x,B)$ is the generating function:

and

The number of permutations that avoid $B$ is