Course contentsShow
← Mathematics
Lesson 2622 of 3,12152. CombinatoricsFree lesson

Derangements and the Derangement Formula

Applying inclusion-exclusion to count permutations with no fixed points.

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.