# §26.15 Permutations: Matrix Notation

The set $\mathop{\mathfrak{S}_{n}\/}\nolimits$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

 26.15.1 $\begin{bmatrix}0&0&1&0&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1\\ 1&0&0&0&0&0&0&0\\ 0&0&0&0&0&1&0&0\end{bmatrix}$ Permalink: http://dlmf.nist.gov/26.15.E1 Encodings: TeX, pMML, png See also: info for 26.15

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$:

 26.15.2 $\mathop{\mathrm{inv}}(\sigma)=\sum a_{gh}a_{k\ell},$ Symbols: $h$: nonnegative integer, $k$: nonnegative integer, $\ell$: nonnegative integer and $\sigma$: permutation Permalink: http://dlmf.nist.gov/26.15.E2 Encodings: TeX, pMML, png See also: info for 26.15

where the sum is over $1\leq g and $n\geq h>\ell\geq 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,\ldots,n\}\times\{1,2,\ldots,n\}$. If $(j,k)\in B$, then $\sigma(j)\neq k$. The number of derangements of $n$ is the number of permutations with forbidden positions $B=\{(1,1),(2,2),\ldots,(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)=\binom{n}{j}$. The rook polynomial is the generating function for $r_{j}(B)$:

 26.15.3 $R(x,B)=\sum_{j=0}^{n}r_{j}(B)\,x^{j}.$

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

 26.15.4 $R(x,B)=R(x,B_{1})\,R(x,B_{2}).$ Symbols: $x$: real variable, $B$: subset and $R(x,B)$: rook polynomial Permalink: http://dlmf.nist.gov/26.15.E4 Encodings: TeX, pMML, png See also: info for 26.15

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,\ldots,n$. $B\setminus(j,k)$ denotes $B$ with the element $(j,k)$ removed.

 26.15.5 $R(x,B)=x\,R(x,B\setminus[j,k])+R(x,B\setminus(j,k)).$

$N_{k}(B)$ is the number of permutations in $\mathop{\mathfrak{S}_{n}\/}\nolimits$ for which exactly $k$ of the pairs $(j,\sigma(j))$ are elements of $B$. $N(x,B)$ is the generating function:

 26.15.6 $N(x,B)=\sum_{k=0}^{n}N_{k}(B)\,x^{k},$

and

 26.15.7 $N(x,B)=\sum_{k=0}^{n}r_{k}(B)(n-k)!(x-1)^{k}.$

The number of permutations that avoid $B$ is

 26.15.8 $N_{0}(B)\equiv N(0,B)=\sum_{k=0}^{n}(-1)^{k}r_{k}(B)(n-k)!.$

## Example 1

The problème des ménages asks for the number of ways of seating $n$ 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 $2(n!)$ ways to place the wives. Let $B=\{(j,j),(j,j+1)\>|\>1\leq j. Then

 26.15.9 $r_{k}(B)=\frac{2n}{2n-k}\binom{2n-k}{k}.$

The solution is

 26.15.10 $2(n!)N_{0}(B)=2(n!)\sum_{k=0}^{n}(-1)^{k}\frac{2n}{2n-k}\binom{2n-k}{k}{(n-k)!}.$

## Example 2

The Ferrers board of shape $(b_{1},b_{2},\ldots,b_{n})$, $0\leq b_{1}\leq b_{2}\leq\cdots\leq b_{n}$, is the set $B=\{(j,k)\>|\>1\leq j\leq n,1\leq k\leq b_{j}\}$. For this set,

 26.15.11 $\sum_{k=0}^{n}r_{n-k}(B)(x-k+1)_{k}=\prod_{j=1}^{n}(x+b_{j}-j+1).$

If $B$ is the Ferrers board of shape $(0,1,2,\ldots,n-1)$, then

 26.15.12 $\sum_{k=0}^{n}r_{n-k}(B)(x-k+1)_{k}=x^{n},$

and therefore by (26.8.10),

 26.15.13 $r_{n-k}(B)=\mathop{S\/}\nolimits\!\left(n,k\right).$