Derangement

A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. 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 elements can be computed in the Wolfram Language using

Derangements[l_List] := With[
  {perms = Permutations[l]},
  {supp = PermutationSupport /@ perms},
  Pick[perms, Length /@ supp, Length[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, and the number of derangements on elements is called the subfactorial of .

The function giving the number of distinct derangements on elements is called the subfactorial and is equal to

			(1)
			(2)

(Bhatnagar 1995, pp. 8-9), where is the incomplete gamma function, or

(3)

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

As the number of objects increases, the probability that none appears in its correct position approaches

(4)

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

The number of derangements of length satisfy the recurrence relations

(5)

and

(6)

with and (Skiena 1990, p. 33). 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).

Wolfram Web Resources