Definition:Derangement

Definition

A derangement is a permutation $f: S \to S$ from a set $S$ to itself where:

$\forall s \in S: \map f s \ne s$

That is, a permutation with no fixed points.

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

Examples

$3$ Element Set

Let $S = \set {1, 2, 3}$ be an arbitrary set with $3$ elements.

The only derangements of $S$ are the permutations $p_1$ and $p_2$ given in $2$-row notation as:

\(\ds p_1\)

\(:\)

\(\ds \begin {pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end {pmatrix}\)

\(\ds p_2\)

\(:\)

\(\ds \begin {pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end {pmatrix}\)

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

• Results about derangements can be found here.

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

• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): derangement
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): derangement