Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.15 Permutations: Matrix Notation

The set 𝔖n26.13) can be identified with the set of n×n 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 j with column σ(j), and 0’s in all other positions. The permutation 35247816 corresponds to the matrix

26.15.1 [0010000000001000010000000001000000000010000000011000000000000100]

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

26.15.2 inv(σ)=aghak,

where the sum is over 1g<kn and nh>1.

The matrix represents the placement of n nonattacking rooks on an n×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{1,2,,n}×{1,2,,n}. If (j,k)B, then σ(j)k. The number of derangements of n is the number of permutations with forbidden positions B={(1,1),(2,2),,(n,n)}.

Let rj(B) be the number of ways of placing j nonattacking rooks on the squares of B. Define r0(B)=1. For the problem of derangements, rj(B)=(nj). The rook polynomial is the generating function for rj(B):

26.15.3 R(x,B)=j=0nrj(B)xj.

If B=B1B2, where no element of B1 is in the same row or column as any element of B2, then

26.15.4 R(x,B)=R(x,B1)R(x,B2).

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

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

Nk(B) is the number of permutations in 𝔖n for which exactly k of the pairs (j,σ(j)) are elements of B. N(x,B) is the generating function:

26.15.6 N(x,B)=k=0nNk(B)xk,

and

26.15.7 N(x,B)=k=0nrk(B)(n-k)!(x-1)k.

The number of permutations that avoid B is

26.15.8 N0(B)N(0,B)=k=0n(-1)krk(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)| 1j<n}{(n,n),(n,1)}. Then

26.15.9 rk(B)=2n2n-k(2n-kk).

The solution is

26.15.10 2(n!)N0(B)=2(n!)k=0n(-1)k2n2n-k(2n-kk)(n-k)!.

Example 2

The Ferrers board of shape (b1,b2,,bn), 0b1b2bn, is the set B={(j,k)| 1jn,1kbj}. For this set,

26.15.11 k=0nrn-k(B)(x-k+1)k=j=1n(x+bj-j+1).

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

26.15.12 k=0nrn-k(B)(x-k+1)k=xn,

and therefore by (26.8.10),

26.15.13 rn-k(B)=S(n,k).