Number of Derangements

Theorem

The total number of derangements of a set with $n$ elements is given by:

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

Proof

A derangement is a permutation that fixes no elements.

So, to compute the total number of derangements, we compute the number of permutations that fix elements, that is leave elements in the same place.

Let $\pi$ be a permutation of $S$.

Let $x, y \in S$.

Let $i$ be a position in a given permutation of set $S$, where $1 \le i \le n$.

Let $P_i \left({\pi}\right)$ be the property that $\pi \left({x}\right) = y$ at position $i$.

If we consider all the permutations of a set where the property $P_i$ holds, we have fixed a single element of the set.

So there are $\left({n-1}\right)!$ such possible permutations.

Furthermore, we could have chosen $i$ as any element in the set so there are $C \left({n, 1}\right)$ terms to choose from.

So $N \left({P_i}\right) = \left({n-1}\right)!$ and there are $C \left({n, 1}\right)$ terms.

Similarly, $N \left({P_i, P_j}\right) = \left({n-2}\right)!$ and there are $C \left({n, 2}\right)$ terms.

So now we can compute the total number of derangements:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle D_n\)	\(=\)	\(\displaystyle n! - C(n,1)(n-1)! + C(n,2)(n-2)! - ... + (-1)^n C(n,n)(n-n)!\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n! - \frac{n!} {1!(n-1)!}(n-1)! + \frac{n!} {2!(n-2)!}(n-2)! \ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n! \left({1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \ldots + \left({-1}\right)^n \frac 1 {n!} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$