Derangement — Definition, Formula & Examples

A derangement is a rearrangement of a set of elements in which none of the elements end up in their original position. For example, if three people each grab a random hat, a derangement occurs when nobody gets their own hat back.

A derangement of a finite set $\{1, 2, \ldots, n\}$ is a permutation $\sigma$ such that $\sigma(i) \neq i$ for every $i \in \{1, 2, \ldots, n\}$ . The number of such permutations is denoted $D_n$ (also written $!n$ , the subfactorial).

Key Formula

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

Where:

$D_n$ = Number of derangements of $n$ elements (also written $!n$)
$n$ = Total number of elements in the set
$k$ = Summation index used in the inclusion-exclusion expansion

How It Works

To count derangements, apply the inclusion-exclusion principle to subtract out all permutations that fix at least one element. Let

A_i

be the set of permutations fixing element

i

. The number of permutations fixing no element is

n!

minus the size of

A_1 \cup A_2 \cup \cdots \cup A_n

, expanded via inclusion-exclusion. This yields the closed-form subfactorial formula. For large

n

D_n

approaches

n!/e

, so the probability that a random permutation is a derangement converges to

1/e \approx 0.3679

Worked Example

Problem: Four friends exchange gifts randomly. In how many ways can the gifts be distributed so that nobody receives their own gift?

Apply the formula: Use the derangement formula with

n = 4

D_4 = 4! \sum_{k=0}^{4} \frac{(-1)^k}{k!}

Expand the sum: Compute each term of the alternating sum.

D_4 = 24\!\left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 24\!\left(\frac{24 - 24 + 12 - 4 + 1}{24}\right)

Simplify: The numerator equals 9.

D_4 = 24 \cdot \frac{9}{24} = 9

Answer: There are 9 ways to distribute the gifts so that nobody receives their own.

Why It Matters

Derangements appear in probability problems involving random matchings — secret Santa draws, shuffled exams, misdelivered letters. They also arise in algebraic combinatorics and the analysis of sorting algorithms where fixed points must be avoided.

Common Mistakes

Mistake: Confusing

D_n

with

n! - 1

, thinking you just remove the identity permutation.

Correction: Many permutations besides the identity fix at least one element. You must exclude all of them, which is exactly what the inclusion-exclusion formula does.