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
![!n=[(n!)/e],](/https/mathworld.wolfram.com/images/equations/Derangement/NumberedEquation1.svg) |
(3)
|
where 
is the usual factorial and ![[x]](/https/mathworld.wolfram.com/images/equations/Derangement/Inline29.svg)
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
![d(n)=(n-1)[d(n-1)+d(n-2)]](/https/mathworld.wolfram.com/images/equations/Derangement/NumberedEquation3.svg) |
(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).
