Definition:Derangement

Definition

A derangement is a permutation $f: S \to S$ from a set $S$ to itself where $\map f s \ne s$ for any $s \in S$.

If $S$ is finite, the number of derangements is denoted by $D_n$ where $n = \card S$ (the cardinality of $S$.)

Also see

• Recurrence Relation for Number of Derangements on Finite Set
• Closed Form for Number of Derangements on Finite Set
• Definition:Subfactorial

• Hat-Check Problem

Historical Note

The number of a derangements of a finite set was first investigated by Nicolaus I Bernoulli and Pierre Raymond de Montmort between about $1708$ and $1713$.

They solved it at around the same time.

The question is often couched in the idea of counting the number of ways of placing letters at random in envelopes such that nobody receives the correct letter.

Sources

• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: derangement