Derangements

Five friends — Aarav, Bhumi, Chirag, Divya, and Esha — each bring a gift to a party and put it in a common pile. Later, each person draws one gift at random. What is the probability that nobody gets their own gift back?

The total number of ways to distribute the five gifts is 5! = 120. The question reduces to: how many of those 120 permutations have the property that no person receives the gift they brought? Such a permutation is called a derangement, and counting derangements is one of the most elegant applications of inclusion-exclusion.

What is a derangement?

For n = 1: the only permutation of \{1\} is (1), which is a fixed point. So D_1 = 0.

For n = 2: the permutations of \{1, 2\} are (1, 2) and (2, 1). Only (2, 1) has no fixed points. So D_2 = 1.

For n = 3: list all 3! = 6 permutations and check:

So D_3 = 2.

Deriving the formula using inclusion-exclusion

The derivation is a direct application of the inclusion-exclusion principle to the "bad" events (fixed points).

Setup. Let A_i be the set of permutations of \{1, 2, \ldots, n\} that fix element i (i.e., \sigma(i) = i). A derangement is a permutation in none of A_1, A_2, \ldots, A_n. So:

Computing the intersection sizes. If a permutation fixes a specific set S of k elements (meaning \sigma(i) = i for all i \in S), the remaining n - k elements can be arranged in any order: (n - k)! permutations. So:

There are \binom{n}{k} ways to choose a set S of size k, so:

Applying inclusion-exclusion. The number of permutations with at least one fixed point is:

where S_k = \binom{n}{k}(n-k)!. Simplifying:

So S_k = \frac{n!}{k!}, and:

The derangement formula. Subtracting from n!:

Factor out n!:

The first several values

The ratio D_n/n! oscillates and converges to 1/e \approx 0.367879\ldots. By n = 5, the ratio is already within 0.2\% of 1/e. This rapid convergence is because the sum \sum_{k=0}^n (-1)^k/k! is the partial sum of the Taylor series for e^{-1}.

Subfactorial notation

The derangement count D_n is also written !n (read "subfactorial n"), placing the exclamation mark on the left instead of the right. This notation emphasises the parallel with n!: while n! counts all permutations, !n counts only the derangements.

A useful way to remember the formula: !n = n! \times (\text{partial sum of the series for } e^{-1}).

The "nearest integer" characterisation also gives a fast computation: calculate n!/e, round to the nearest integer, and that is D_n. For n = 5: 120/e \approx 120/2.71828 \approx 44.146, which rounds to 44 = D_5.

Solving the gift exchange problem

Return to the five friends with gifts. The number of ways nobody gets their own gift is D_5:

Compute the sum inside the parentheses: \frac{60 - 20 + 5 - 1}{120} = \frac{44}{120}.

So D_5 = 120 \times \frac{44}{120} = 44.

The probability that nobody gets their own gift: \frac{D_5}{5!} = \frac{44}{120} = \frac{11}{30} \approx 36.7\%.

Remarkably, if the party had 50 friends instead of 5, the probability would still be approximately 1/e \approx 36.8\%. The number of people barely affects the probability — once n \geq 5, the fraction is essentially locked at 1/e.

Two worked examples

Common confusions

• "D_n = n! - 1 (just remove the identity permutation)." This only removes the permutation where every element is fixed. Derangements require that no element is fixed. There are many permutations with some (but not all) fixed points, and those are not derangements either.

• "D_1 = 1." There is no derangement of a single element — the only permutation of \{1\} is (1), which fixes element 1. So D_1 = 0.

• "The probability of a derangement depends heavily on n." For n \geq 5, the probability is nearly constant at 1/e \approx 0.368. The convergence is so fast that the dependence on n is negligible in practice.

• "Derangements have nothing to do with inclusion-exclusion." The derivation is a textbook application of inclusion-exclusion. The "bad" sets are A_i = \{\text{permutations fixing } i\}, and the derangement count is n! - |A_1 \cup \cdots \cup A_n|.

• "To count permutations with exactly m fixed points, subtract D_{n-m} from n!." The correct formula is \binom{n}{m} \times D_{n-m}: first choose which m elements are fixed, then derange the remaining n - m.

Going deeper

The recursion for D_n

Derangements satisfy two recursions:

Recursion 1: D_n = (n-1)(D_{n-1} + D_{n-2}) for n \geq 3, with D_1 = 0, D_2 = 1.

Why this works. Consider element 1. In a derangement, \sigma(1) = j for some j \neq 1. There are n - 1 choices for j. Now look at what happens to position j (where does element j go?):

• Case A: \sigma(j) = 1. Elements 1 and j swap, and the remaining n - 2 elements must form a derangement among themselves. There are D_{n-2} such derangements.

• Case B: \sigma(j) \neq 1. Element j cannot go to position j (derangement condition) and also does not go to position 1. Effectively, element j plays the role of element 1 in a derangement of n - 1 objects. There are D_{n-1} such derangements.

Total: (n-1)(D_{n-1} + D_{n-2}).

Recursion 2: D_n = nD_{n-1} + (-1)^n for n \geq 2.

This follows from the closed-form formula. It gives a fast way to compute D_n from D_{n-1}: multiply by n and adjust by \pm 1.

From D_4 = 9: D_5 = 5 \times 9 + (-1)^5 = 45 - 1 = 44. From D_5 = 44: D_6 = 6 \times 44 + (-1)^6 = 264 + 1 = 265.

The hat-check problem

The derangement problem is classically called the "hat-check problem" or the probleme des rencontres (problem of coincidences): n guests check their hats, and the hats are returned at random. What is the probability that no guest gets their own hat? The answer, 1/e, has been known since the early 1700s. The rapid convergence to 1/e means that whether there are 5 guests or 500, the probability is nearly the same — an unintuitive but beautiful fact.

Derangements and the exponential function

The connection between D_n and e^{-1} is not a coincidence. The Taylor series for e^x evaluated at x = -1 gives:

The derangement formula D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} is exactly n! times the n-th partial sum of this series. As n \to \infty, the partial sum approaches e^{-1}, so D_n/n! \to 1/e. The error in truncating the series at the n-th term is at most 1/(n+1)!, which is less than 1 for n \geq 0. This is why D_n is always the integer nearest to n!/e.

Where this leads next

• Inclusion-Exclusion Principle — the counting tool that derives the derangement formula.
• Permutations — Basics — the n! total permutations from which derangements are drawn.
• Factorial Notation — the notation n! and !n (subfactorial) used throughout this article.
• Permutations — Special Cases — permutations with restrictions, of which derangements are the most famous example.
• Combinations — Basics — the \binom{n}{m} factor that appears in counting permutations with exactly m fixed points.