Skip to content

Derangements

Derangement

Definition

A derangement is a permutation in which no element appears in its original position. That is, for a permutation \(P\) of \(1\sim n\), if \(P_i\neq i\) holds for all \(i\), then \(P\) is called a derangement of \(n\).

For example, the derangements of three elements are \(\{2,3,1\}\) and \(\{3,1,2\}\). The derangements of four elements 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 points, i.e., no cycles of length 1.

Calculation via Inclusion-Exclusion Principle

The universal set \(U\) is the set of all permutations of \(1\sim n\), with \(|U|=n!\). The property is \(P_i\neq i\). Applying the complement formula, the problem becomes finding \(\left|\bigcup_{i=1}^n\overline{S_i}\right|\).

It is known that \(\overline{S_i}\) represents the number of permutations satisfying \(P_i=i\). Expanding the expression using the inclusion-exclusion principle requires calculating the size of intersections of specific sets, i.e.:

\[ \left|\bigcap_{i=1}^{k}S_{a_i}\right| \]

Here, the condition \(a_i<a_{i+1}\) is omitted for convenience. The intersection of these \(k\) sets represents the number of permutations where \(k\) variables satisfy \(P_{a_i}=a_i\), while the remaining \(n-k\) elements can be placed arbitrarily. Thus, the number of such permutations is:

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

The number of ways to choose \(k\) elements is \(\dbinom{n}{k}\), so:

\[ \begin{aligned} \left|\bigcup_{i=1}^n\overline{S_i}\right| &=\sum_{k=1}^n(-1)^{k-1}\sum_{a_{1,\cdots,k} }\left|\bigcap_{i=1}^{k}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\) 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).

Calculation via Recurrence

To make the derangement problem more concrete, consider the following problem:

There are \(n\) distinct letters, numbered \(1,2,3,4,5\), and \(n\) envelopes numbered \(1,2,3,4,5\). The letters are to be placed in the envelopes such that no letter is placed in the envelope with the same number. How many different ways are there to place the letters?

Assume we consider the \(n\)-th envelope. Initially, temporarily place the \(n\)-th letter in the \(n\)-th envelope, then consider two cases for recurrence:

  • The first \(n-1\) envelopes are all misplaced;
  • Among the first \(n-1\) envelopes, exactly one is correctly placed, and the rest are all misplaced.

For the first case, where the first \(n-1\) envelopes are all misplaced: Since the first \(n-1\) are all misplaced, the \(n\)-th letter only needs to swap with any one of the previous positions. There are \(D_{n-1}\times (n-1)\) such cases.

For the second case, where among the first \(n-1\) envelopes, exactly one is correctly placed and the rest are misplaced: The purpose of considering this case is that if one of the first \(n-1\) envelopes is correctly placed, swapping that correctly placed letter with the \(n\)-th letter yields a full derangement of length \(n\).

Other cases cannot be turned into a derangement of length \(n\) through a single operation.

Thus, the number of derangements satisfies the recurrence relation:

\[ D_n=(n-1)(D_{n-1}+D_{n-2}) \]

Another recurrence relation is also given:

\[ D_n=nD_{n-1}+{(-1)}^n \]

Other Relations

The number of derangements has a simple floor/ceiling expression, and its growth rate differs from the factorial only by a constant:

\[ D_n=\begin{cases} \left\lceil\frac{n!}{\mathrm{e}}\right\rceil, & \text{if }n\text{ is even}, \\ \left\lfloor\frac{n!}{\mathrm{e}}\right\rfloor, & \text{if }n\text{ is odd}. \end{cases} \]

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}} \]
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用