Derangement

A derangement is a permutation of distinct objects in which none remains in its original position. For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and . Derangements are permutations without fixed points (i.e., having no cycles of length one). The derangements of a list of distinct elements, relative to their positions in that list, can be computed in the Wolfram Language using

Derangements[l_List] := DeleteCases[
 Permutations[l],
 p_ /; Or @@ MapThread[SameQ, {p, l}]
]

The derangement problem was formulated by P. R. de Montmort in 1708, and solved by him in 1713 (de Montmort 1713-1714). Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8).

Derangements are also called rencontres numbers (named after rencontres solitaire) or complete permutations. The number of derangements of distinct elements is the subfactorial . For integers , it is given by

			(1)
			(2)

(Bhatnagar 1995, pp. 8-9), where is the incomplete gamma function. For , it also equals

(3)

where is the usual factorial and is the nearest integer function.

For a uniformly random permutation of distinct objects, the probability that none remains in its original position is . As increases, this probability approaches

(4)

(Wells 1986, p. 27). In fact, the probability is very close to already even for as few as four points.

The numbers of derangements satisfy the recurrence relations

(5)

for and

(6)

for , with and (Skiena 1990, p. 33). For , 2, ..., the first few are 0, 1, 2, 9, 44, 265, 1854, ... (OEIS A000166). The recurrence can be solved exactly, although the sequence of cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, pp. 157-160; Koepf 1998, p. 159).