Definition
In combinatorial mathematics, a derangement is a permutation of a set of elements in which none of the elements appear in their original positions. Formally, for a set $S={1,2,\dots ,n}$, a permutation $\sigma$ is a derangement if $\sigma(i)
eq i$ for every $i\in S$.
Notation
The number of derangements of $n$ distinct objects is commonly denoted by $!n$ (read “subfactorial $n$”) or $D_n$.
Counting Formula
The exact count is given by
$$
!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}
= \left\lfloor \frac{n!}{e} + \frac{1}{2}\right\rfloor ,
$$
where $e$ is the base of the natural logarithm and $\lfloor\cdot\rfloor$ denotes the floor function.
A recurrence relation also holds:
$$
!0 = 1,\qquad !1 = 0,\qquad
!n = (n-1)\bigl(!(n-1) + !(n-2)\bigr)\ \text{for } n\ge 2.
$$
Examples
- For $n=2$, the only permutation $(2,1)$ is a derangement, so $!2 = 1$.
- For $n=3$, the permutations $(2,3,1)$ and $(3,1,2)$ are derangements, giving $!3 = 2$.
Applications
Derangements appear in probability problems such as the “matching problem” (also known as the “hat‑check problem”), where one asks for the probability that none of $n$ people receive their own hat when hats are returned at random. The probability converges to $1/e \approx 0.3679$ as $n$ grows large.
Historical Notes
The problem of counting derangements dates back to Pierre‑Rene de Fermat (1640) and was later studied by Blaise Pascal and Étienne Bézout. The explicit inclusion–exclusion derivation was formalized by Pierre de Montmort in his 1713 work Essay d’analyse sur les jeux de hasard.
Related Concepts
- Inclusion–Exclusion Principle: The standard derivation of the derangement formula uses this principle.
- Permutation: A bijective mapping of a set onto itself; derangements are a special class of permutations.
- Subfactorial: Another term for the derangement number, denoted $!n$.
References
- Graham, R. L.; Knuth, D. E.; Patashnik, O. Concrete Mathematics, 2nd ed., Addison‑Wesley, 1994.
- Stanley, R. P. Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.
All statements above are based on established mathematical literature.
