Derangements and the Derangement Formula
What you'll learn: How to use the inclusion-exclusion principle to count permutations where no element stays in its original position.
The Core Idea
A derangement is a permutation where nothing is where it started—no "fixed points." You've already seen derangements as a concept; now we derive the exact formula using inclusion-exclusion.
Think of it like a Secret Santa gone right: you have n people, each originally assigned a number from 1 to n. A derangement is a rearrangement where person i never gets their own original number i.
Applying Inclusion-Exclusion
Let's count derangements of n objects.
Define property Pᵢ as "object i is in position i" (a fixed point). We want permutations with none of these properties—exactly what we learned in "Counting with None of the Properties"!
- Total permutations: n!
- Permutations with at least one fixed point: use inclusion-exclusion
- Objects satisfying P₁: fix position 1, arrange rest = (n-1)!
- Objects satisfying P₁ ∩ P₂: fix positions 1 and 2 = (n-2)!
- And so on...
By inclusion-exclusion:
|P₁ ∪ P₂ ∪ ... ∪ Pₙ| = C(n,1)·(n-1)! - C(n,2)·(n-2)! + C(n,3)·(n-3)! - ... ± C(n,n)·0!
Simplifying (since C(n,k)·(n-k)! = n!/k!):
Number of derangements D(n) = n! - n!/1! + n!/2! - n!/3! + ... ± n!/n!
= n! · (1 - 1/1! + 1/2! - 1/3! + ... ± 1/n!)
This alternating sum is the inclusion-exclusion principle in action!
Key Takeaway: The derangement formula D(n) = n! Σ (-1)ᵏ/k! (sum from k=0 to n) counts permutations with no fixed points by systematically subtracting and adding back overcounted cases using inclusion-exclusion.