Derangement

Number of possible permutations and derangements of Template:Mvar elements. Template:Math (Template:Mvar factorial) is the number of Template:Mvar-permutations; Template:Math is the number of derangements – Template:Mvar-permutations where all of the Template:Mvar elements change their initial places.

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.

The number of derangements of a set of size Template:Mvar is known as the Template:Nobr derangement number or the subfactorial of Template:Mvar or Template:Nobr de Montmort number (after Pierre Remond de Montmort). Notations for subfactorials in common use include Template:Math, Template:Math, Template:Math, or Template:Math .Template:Efn

For Template:Math, the subfactorial Template:Math equals the nearest integer to Template:Math, where Template:Math denotes the factorial of Template:Mvar and Template:Math is Euler's number.

The problem of counting derangements was first considered by Pierre Raymond de Montmort in his Essay d'analyse sur les jeux de hazard in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time.

Example

The 9 derangements (from 24 permutations) are highlighted.

Suppose that a professor gave a test to 4 students – A, B, C, and D – and wants to let them grade each other's tests. How many ways could the professor hand the tests back to the students for grading, such that no student receives their own test back? Out of 24 possible permutations (4!) for handing back the tests,

ABCD,	ABDC,	ACBD,	ACDB,	ADBC,	ADCB,
BACD,	BADC,	BCAD,	BCDA,	BDAC,	BDCA,
CABD,	CADB,	CBAD,	CBDA,	CDAB,	CDBA,
DABC,	DACB,	DBAC,	DBCA,	DCAB,	DCBA.

there are only 9 derangements (shown in blue italics above). In every other permutation of this 4-member set, at least one student gets their own test back (shown in bold red).

Another version of the problem arises when we ask for the number of ways Template:Mvar letters, each addressed to a different person, can be placed in Template:Mvar pre-addressed envelopes so that no letter appears in the correctly addressed envelope.

Counting derangements

Counting derangements of a set amounts to the hat-check problem, in which one considers the number of ways in which Template:Math hats (call them Template:Math through Template:Math) can be returned to Template:Math people (Template:Math through Template:Math) such that no hat makes it back to its owner.

Each person may receive any of the Template:Math hats that is not their own. Call the hat which the person Template:Math receives Template:Math and consider Template:MathTemplate:'s owner: Template:Math receives either Template:MathTemplate:'s hat, Template:Math, or some other. Accordingly, the problem splits into two possible cases:

1. Template:Math receives a hat other than Template:Math. This case is equivalent to solving the problem with Template:Math people and Template:Math hats because for each of the Template:Math people besides Template:Math there is exactly one hat from among the remaining Template:Math hats that they may not receive (for any Template:Math besides Template:Math, the unreceivable hat is Template:Math, while for Template:Math it is Template:Math). Another way to see this is to rename Template:Math to Template:Math, where the derangement is more explicit: for any Template:Math from 2 to Template:Math, Template:Math cannot receive Template:Math.
2. Template:Math receives Template:Math. In this case the problem reduces to Template:Math people and Template:Math hats, because Template:Math received Template:MathTemplate:'s hat and Template:Math received Template:MathTemplate:'s hat, effectively putting both out of further consideration.

For each of the Template:Math hats that Template:Math may receive, the number of ways that Template:Math may all receive hats is the sum of the counts for the two cases.

This gives us the solution to the hat-check problem: Stated algebraically, the number Template:Math of derangements of an Template:Math-element set is $$D_n=(n-1)(D_{n-1}+D_{n-2})\text{for}n\ge 2,$$ where Template:Math and Template:Math.

The number of derangements of small lengths is given in the table below. Template:Clear

The number of derangements of an Template:Math-element set Template:OEIS for small Template:Math

Template:Math	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Template:Math	1	0	1	2	9	44	265	1,854	14,833	133,496	1,334,961	14,684,570	176,214,841	2,290,792,932

There are various other expressions for Template:Math, equivalent to the formula given above. These include $$D_n=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}\text{for}n\ge 0$$ and $$D_n=\left[\frac{n!}{e}\right]=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor \text{for}n\ge 1,$$ where Template:Math is the nearest integer function and Template:Math is the floor function.

Other related formulas include $$\begin{array}{cccc}{D}_n& =\lfloor \frac{n!+1}{e}\rfloor & \text{for}n& \ge 1,\\ D_n& =\lfloor (e+e^{-1})n!\rfloor -\lfloor en!\rfloor & \text{for}n& \ge 2,\\ D_n& =n!-\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n}{i})\cdot D_{n-i}& \text{for}n& \ge 1.\end{array}$$

The following recurrence also holds: $$D_n=\{\begin{array}{cc}1& \text{if }n=0,\\ n\cdot D_{n-1}+(-1{)}^n& \text{if }n>0.\end{array}$$

Derivation by inclusion–exclusion principle

One may derive a non-recursive formula for the number of derangements of an Template:Math-set, as well. For Template:Math we define Template:Math to be the set of permutations of Template:Mvar objects that fix the Template:Nobr object. Any intersection of a collection of Template:Mvar of these sets fixes a particular set of Template:Mvar objects and therefore contains Template:Math permutations. There are $(\genfrac{}{}{0ex}{}{n}{i})$ such collections, so the inclusion–exclusion principle yields $$\begin{array}{cc}|S_1\cup \cdots \cup S_n|& =\sum _i\left|S_i\right|-\sum _{i<j}|S_i\cap S_j|+\sum _{i<j<k}|S_i\cap S_j\cap S_k|+\cdots +(-1{)}^{n+1}|S_1\cap \cdots \cap S_n|\\ & =(\genfrac{}{}{0ex}{}{n}{1})(n-1)!-(\genfrac{}{}{0ex}{}{n}{2})(n-2)!+(\genfrac{}{}{0ex}{}{n}{3})(n-3)!-\cdots +(-1{)}^{n+1}(\genfrac{}{}{0ex}{}{n}{n})0!\\ & =\sum _{i=1}^n(-1{)}^{i+1}(\genfrac{}{}{0ex}{}{n}{i})(n-i)!\\ & =n!\sum _{i=1}^n\frac{(-1{)}^{i+1}}{i!},\end{array}$$ and since a derangement is a permutation that leaves none of the Template:Math objects fixed, this implies $$D_n=n!-|S_1\cup \cdots \cup S_n|=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}.$$

On the other hand, $$n!=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})D_i$$ since we can choose Template:Math elements to be in their own place and derange the other Template:Mvar elements in just Template:Math ways, by definition.

Growth rate

From $$D_n=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}$$ and $$e^x=\sum _{i=0}^{\mathrm{\infty }}\frac{x^i}{i!}$$ by substituting Template:Math one immediately obtains that $$\underset{n\to \mathrm{\infty }}{lim}\frac{D_n}{n!}=\underset{n\to \mathrm{\infty }}{lim}\sum _{i=0}^n\frac{(-1{)}^i}{i!}=e^{-1}\approx 0.367879\dots .$$ This is the limit of the probability that a randomly selected permutation of a large number of objects is a derangement. The probability converges to this limit extremely quickly as Template:Mvar increases, which is why Template:Math is the nearest integer to Template:Math. The above semi-log graph shows that the derangement graph lags the permutation graph by an almost constant value.

More information about this calculation and the above limit may be found in the article on the statistics of random permutations.

Asymptotic expansion in terms of Bell numbers

An asymptotic expansion for the number of derangements in terms of Bell numbers is as follows: $$D_n=\frac{n!}{e}+\sum _{k=1}^m{(-1)}^{n+k-1}\frac{B_k}{n^k}+O\left(\frac{1}{n^{m+1}}\right),$$ where Template:Mvar is any fixed positive integer, and Template:Math denotes the Template:Nobr Bell number. Moreover, the constant implied by the [[big O notation|big Template:Mvar]]-term does not exceed Template:Math.

Generalizations

The problème des rencontres asks how many permutations of a size-Template:Math set have exactly Template:Math fixed points.

Derangements are an example of the wider field of constrained permutations. For example, the ménage problem asks if Template:Math opposite-sex couples are seated man–woman–man–woman–… around a table, how many ways can they be seated so that nobody is seated next to his or her partner?

More formally, given sets Template:Math and Template:Math, and some sets Template:Math and Template:Math of surjections Template:Math, we often wish to know the number of pairs of functions Template:Math such that Template:Math is in Template:Math and Template:Math is in Template:Math, and for all Template:Math, Template:Math; in other words, where for each Template:Math and Template:Math, there exists a derangement Template:Math of Template:Math such that Template:Math.

Another generalization is the following problem:

For instance, for a word made of only two different letters, say Template:Math letters A and Template:Math letters B, the answer is, of course, 1 or 0 according to whether Template:Math or not, for the only way to form an anagram without fixed letters is to exchange all the A with B, which is possible if and only if Template:Math. In the general case, for a word with Template:Math letters Template:Math, Template:Math letters Template:Math, …, Template:Math letters Template:Math, it turns out (after a proper use of the inclusion-exclusion formula) that the answer has the form $${\int }_0^{\mathrm{\infty }}{P}_{n_1}(x)P_{n_2}(x)\cdots P_{n_r}(x)e^{-x}dx,$$ for a certain sequence of polynomials Template:Math, where Template:Math has degree Template:Math. But the above answer for the case Template:Math gives an orthogonality relation, whence the Template:Math are the Laguerre polynomials (up to a sign that is easily decided).

Template:Math in the complex plane

In particular, for the classical derangements, one has that $$D_n=\frac{\mathrm{\Gamma }(n+1,-1)}{e}={\int }_0^{\mathrm{\infty }}(x-1{)}^n{e}^{-x}dx$$ where Template:Math is the upper incomplete gamma function.

Computational complexity

It is NP-complete to determine whether a given permutation group (described by a given set of permutations that generate it) contains any derangements.

External links

• Template:Cite web
• Template:Cite web
• Template:Cite web