Toolkit 106

Derangements and Inclusion–Exclusion

A derangement is a permutation in which no element is in its original position.

\pi_i\ne i\qquad(1\le i\le n)

Let D_n denote the number of derangements of 1,2,\dots,n.

D_n=n!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!}\right)

Proof

Suppose the permutation is

\pi_1,\pi_2,\ldots,\pi_n.

For each $i$ , define

A_i=\{\pi_i=i\},\qquad i=1,2,\ldots,n.

A derangement has no fixed points, so

D_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|.

By the Principle of Inclusion–Exclusion,

D_n=n!-\sum |A_i|+\sum |A_i\cap A_j|-\sum |A_i\cap A_j\cap A_k|+\cdots+(-1)^n|A_1\cap A_2\cap\cdots\cap A_n|.

If $k$ specified elements are fixed, the remaining $n-k$ elements can be permuted in $(n-k)!$ ways. Therefore,

D_n=n!-n(n-1)!+\binom{n}{2}(n-2)!-\binom{n}{3}(n-3)!+\cdots+(-1)^n\binom{n}{n}0!.

Factoring out $n!$ gives

D_n=n!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!}\right).

D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.\quad\square