Derangements

Derangements

Definition

A derangement is a permutation in which no element appears in its original position. In other words, for a permutation of $1\sim n$ denoted by $P$, if $P_i\neq i$, then $P$ is called a derangement of $n$.

For example, the ternary derangements are $\{2,3,1\}$ and $\{3,1,2\}$. The quaternary derangements are $\{2,1,4,3\}$, $\{2,3,4,1\}$, $\{2,4,1,3\}$, $\{3,1,4,2\}$, $\{3,4,1,2\}$, $\{3,4,2,1\}$, $\{4,1,2,3\}$, $\{4,3,1,2\}$, and $\{4,3,2,1\}$. A derangement is a permutation with no fixed point, that is, with no cycle of length 1.

Computing with the Inclusion–Exclusion Principle

The universal set $U$ is the set of permutations of $1\sim n$, so $|U|=n!$; let $S_i$ be the permutations in which $P_i\neq i$. Using complements and the inclusion–exclusion principle, the problem becomes finding:

$$\begin{aligned} \left|\bigcap_{i=1}^n S_i\right| &=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|\\ &=n!-\sum_{k=1}^n(-1)^{k-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{k}\overline{S_{a_i}}\right| \end{aligned}$$

Here the summation means choosing from $1, 2, \cdots, n$ the numbers $a_1, a_2, \cdots, a_k$ such that $a_i<a_{i+1}$. Therefore

$$\left|\bigcap_{i=1}^{k}\overline{S_{a_i}}\right|$$

This is the number of permutations in which the $k$ numbers $a_1,a_2,\cdots,a_k$ satisfy $P_{a_i}=a_i$, while the remaining $n-k$ positions can contain any permutation. Hence:

$$\left|\bigcap_{i=1}^{k}\overline{S_{a_i}}\right|=(n-k)!$$

There are $k$ numbers, with $\dbinom{n}{k}$ possible choices, so summing gives:

$$\begin{aligned} &\sum_{k=1}^n(-1)^{k-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{k}\overline{S_{a_i}}\right|\\ =&\sum_{k=1}^n(-1)^{k-1}\dbinom{n}{k}(n-k)!\\ =&\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\\ =&n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!} \end{aligned}$$

Therefore, the number of derangements of $n$ elements is:

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

The first few terms of the derangement sequence are $0,1,2,9,44,265$ (OEIS A000166).

Computing by Recurrence

Let us make the derangement problem concrete by considering the following question:

$n$ distinct letters, numbered $1,2,3,4,5$, are to be placed into envelopes numbered $1,2,3,4,5$, with no envelope number matching the letter number. How many different placements are possible?

Suppose we consider the $n$-th envelope and initially place the $n$-th letter into the $n$-th envelope temporarily. We then derive a recurrence from two cases:

• All of the first $n-1$ envelopes contain the wrong letters;
• Exactly one of the first $n-1$ envelopes contains the correct letter, and all the others contain the wrong letters.

In the first case, all of the first $n-1$ envelopes contain the wrong letters. Since the first $n-1$ envelopes are already all wrong, the $n$-th letter only needs to be swapped with any one of the preceding positions, giving $D_{n-1}\times (n-1)$ possibilities.

In the second case, exactly one of the first $n-1$ envelopes contains the correct letter, and all the others contain the wrong letters. We consider this case because if one of the first $n-1$ envelopes is correct, swapping that letter with the $n$-th letter produces a derangement.

In all other cases, a single operation cannot turn the arrangement into a derangement of length $n$.

Thus, the number of derangements satisfies the recurrence:

$$D_n=(n-1)(D_{n-1}+D_{n-2})$$

Here is another recurrence:

$$D_n=nD_{n-1}+{(-1)}^n$$

Other Relations

The number of derangements has a simple rounding formula, and its growth differs from the factorial by only a constant factor:

$$D_n=\left\lfloor\frac{n!}{\mathrm{e}} + \frac{1}{2}\right\rfloor$$

As the number of elements increases, the probability P of forming a derangement approaches:

$$P=\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}}$$