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
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
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).