26 Combinatorial Analysis Properties 26.14 Permutations: Order Notation 26.16 Multiset Permutations

§26.15 Permutations: Matrix Notation

Notes:: See Stanley (1997, pp. 71–76), Tucker (2006, pp. 335–345).
Keywords:: permutations, rook polynomial
Referenced by:: ¶ ‣ §26.18
Permalink:: http://dlmf.nist.gov/26.15

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

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:: : nonnegative integer, : nonnegative integer, $\ell$ : nonnegative integer and $\sigma$ : permutation
Permalink:: http://dlmf.nist.gov/26.15.E2
Encodings:: TeX, pMML, png

where the sum is over $1\leq g<k\leq n$ and $n\geq h>\ell\geq 1$ .

The matrix represents the placement of 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 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 nonattacking rooks on the squares of . 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}.$

Symbols:: : real variable, : nonnegative integer, : nonnegative integer, : subset, $r_{j}(B)$ : number of rook positions and : rook polynomial
Permalink:: http://dlmf.nist.gov/26.15.E3
Encodings:: TeX, pMML, png

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:: : real variable, : subset and : rook polynomial
Permalink:: http://dlmf.nist.gov/26.15.E4
Encodings:: TeX, pMML, png

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

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

Symbols:: : closed interval, : open interval, $\setminus$ : set subtraction, : real variable, : nonnegative integer, : nonnegative integer, : subset and : rook polynomial
Permalink:: http://dlmf.nist.gov/26.15.E5
Encodings:: TeX, pMML, png

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

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

Symbols:: : real variable, : nonnegative integer, : nonnegative integer, : subset and : generating function
Permalink:: http://dlmf.nist.gov/26.15.E6
Encodings:: TeX, pMML, png

and

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

Symbols:: : : factorial, : real variable, : nonnegative integer, : nonnegative integer, : subset, $r_{j}(B)$ : number of rook positions and : generating function
Permalink:: http://dlmf.nist.gov/26.15.E7
Encodings:: TeX, pMML, png

The number of permutations that avoid is

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

Symbols:: : : factorial, : nonnegative integer, : nonnegative integer, : subset, $r_{j}(B)$ : number of rook positions and : generating function
Permalink:: http://dlmf.nist.gov/26.15.E8
Encodings:: TeX, pMML, png

¶ Example 1

Keywords:: problème des ménages

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 $B=\{(j,j),(j,j+1)\>|\>1\leq j<n\}\cup\{(n,n),(n,1)\}$ . Then

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

Symbols:: $\binom{m}{n}$ : binomial coefficient, : nonnegative integer, : nonnegative integer, : subset and $r_{j}(B)$ : number of rook positions
Permalink:: http://dlmf.nist.gov/26.15.E9
Encodings:: TeX, pMML, png

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% )!}.$

Symbols:: $\binom{m}{n}$ : binomial coefficient, : : factorial, : nonnegative integer, : nonnegative integer, : subset and : generating function
Permalink:: http://dlmf.nist.gov/26.15.E10
Encodings:: TeX, pMML, png

¶ Example 2

Keywords:: Ferrers board

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,