Derangements via I-E

Combinatorics · Axiom Academy

Deriving the derangement formula using the Inclusion-Exclusion Principle We want to count permutations of n elements where no element is in its original position . Let's define: Universe: All n! permutations of n elements A i : Set of permutations where element i is fixed (in position i) Goal: Count permutations in none of the A i sets By Inclusion-Exclusion, this equals the complement: all permutations minus those with at least one fixed point. 2. Applying Inclusion-Exclusion Add permutations with at least 1 fixed element: |A 1 ∪ A 2 ∪ ... ∪ A n | Use I-E expansion: Sum over all intersections with alternating signs Key insight: |A i₁ ∩ A i₂ ∩ ... ∩ A iₖ | = (n-k)! because k positions are fixed The number of ways to choose k elements from n is C(n,k), so each term of size k appears C(n,k) times. Starting with the I-E expansion, we compute each term: Permutations with ≥1 fixed: C(n,1) × (n-1)! = n!/1! Permutations with ≥2 fixed: C(n,2) × (n-2)! = n!/2! Permutations with ≥k fixed: C(n,k) × (n-k)! = n!/k! The I-E formula alternates signs. Subtract from n! to get derangements: Factor out n! from the expression to get the elegant final formula: Notice that as n → ∞, this approaches n!/e ≈ 0.368 × n! , meaning approximately 36.8% of all permutations are derangements!

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