Derangements

Combinatorics · Axiom Academy

Permutations where no element remains in its original position We denote the number of derangements of n objects as D(n). This is also called a "permutation with no fixed points." The Hat-Check Problem: At a party, n guests check their hats. When leaving, the confused attendant returns the hats completely at random. What is the number of ways that no guest receives their own hat? 2. Small Cases: Building Intuition Let's explore derangements for small values of n to understand the pattern: n = 1: With one element [1], there are no derangements (we can't move it away from position 1). Thus D(1) = 0 . n = 2: For [1, 2], only [2, 1] is a derangement. Thus D(2) = 1 . n = 3: For [1, 2, 3], the derangements are [2, 3, 1] and [3, 1, 2]. Thus D(3) = 2 . n = 4: There are exactly D(4) = 9 derangements of four elements. Notice how the count grows quickly but not as fast as n! (which counts all permutations). The ratio D(n)/n! approaches 1/e as n grows. Using the inclusion-exclusion principle , we can derive a beautiful formula for D(n). We start with all n! permutations and subtract those with at least one fixed point, add back those with at least two fixed points, and so on. This leads to the exact formula: where the sum runs from k = 0 to k = n. 4. The Remarkable Approximation One of the most striking facts about derangements is that for even moderately sized n, the number of derangements is approximately:

This is the written version of the interactive lesson above. See the full Combinatorics course.