Derangements

Count permutations with no fixed points using inclusion-exclusion, and use the e^{-1} approximation.

1. The idea

A derangement is a permutation of $n$ objects in which no object ends up in its original position — every element is displaced. This is exactly the classic 'mismatched hats' or 'misdelivered letters' problem.

Applying inclusion-exclusion to the events 'object $i$ is in its original position' gives the derangement formula $D_{n} = n! \sum_{i = 0}^{n} \frac{( - 1 ) ^{i}}{i !}$ , which can also be written as the nearest-integer rounding of $n! / e$ for $n \geq 1$ .

As $n$ grows, the fraction of permutations that are derangements converges quickly to $1/ e \approx 0.3679$ , so even for a moderate $n$ like 10, roughly 37% of all permutations have no fixed points.

2. Why it matters

Derangements are a textbook inclusion-exclusion application with a clean closed form, and the $e^{- 1}$ limit is a fast sanity check and estimation tool for larger n in interviews.

3. Core mathematics

Derangement formula

D_{n} = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}

Approximation

D_{n} \approx \frac{n !}{e}

Exact value is the nearest integer to $n! / e$ for $n \geq 1$ .

Recurrence

D_{n} = (n - 1) (D_{n - 1} + D_{n - 2}), D_{0} = 1, D_{1} = 0

4. How to recognize it

Think of this when…

The problem describes items returned to the wrong original owner (hats, letters, gifts) with none matching.
"No fixed points" or "nobody gets their own item back" language.
You need the probability that a random permutation has zero fixed points.
The count or probability is requested for large $n$ , suggesting the $1/ e$ approximation.

5. Worked example

Worked example

5 people check their hats and they are returned randomly. What is the probability that no one gets their own hat back?

1
Total permutations of 5 hats: $5! = 120$ .
2
Compute the derangement count using the formula.
$D_{5} = 5! (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}) = 120 (\frac{44}{120}) = 44$
3
Probability is $D_{5} /5!$ .
$P = \frac{44}{120} = \frac{11}{30} \approx 0.3667$
Answer: $P (no matches) = 44/120 = 11/30 \approx 0.367$ , close to $1/ e \approx 0.3679$ .

6. Common mistakes

Confusing derangements (zero fixed points) with permutations having at least one fixed point — these use complementary counts.
Forgetting the alternating signs in the inclusion-exclusion sum for $D_{n}$ .
Using the $n! / e$ approximation for small $n$ without rounding to the nearest integer, giving a non-integer 'count'.
Misapplying the derangement recurrence with wrong base cases ( $D_{0} = 1$ , not 0).

7. Quick check

What is $D_{4}$ , the number of derangements of 4 objects?

As $n \to \infty$ , the fraction of permutations that are derangements approaches:

8. Practice

25 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Inclusion-Exclusion

Create a free account to save lesson progress.

Recommended next lessonThe Gap Method →