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

Derangements

Explore permutations where no object appears in its original position and introduce derangement formulas.

Derangements

What You'll Learn

You'll learn how to count permutations where every single object ends up in a different position from where it started.

What Is a Derangement?

A derangement is a permutation of objects where no object appears in its original position. Think of it as the "complete chaos" arrangement—nothing stays where it belongs.

Example: If you have hats labeled 1, 2, 3 for three people (also labeled 1, 2, 3), a derangement ensures person 1 doesn't get hat 1, person 2 doesn't get hat 2, and person 3 doesn't get hat 3. For three items, the derangements are:

  • (2, 3, 1): person 1 gets hat 2, person 2 gets hat 3, person 3 gets hat 1
  • (3, 1, 2): person 1 gets hat 3, person 2 gets hat 1, person 3 gets hat 2

That's 2 derangements out of 3! = 6 total permutations.

The Derangement Formula

The number of derangements of n objects is denoted D(n) or !n, and can be calculated using:

D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + 1/4! - ... + (-1)^n/n!)

Or equivalently, the recurrence relation:

  • D(0) = 1 (by convention)
  • D(1) = 0 (one object must stay in place)
  • D(n) = (n - 1) × [D(n - 1) + D(n - 2)] for n ≥ 2

Quick values: D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44

Interestingly, D(n)/n! approaches 1/e ≈ 0.368 as n grows, meaning roughly 37% of all permutations are derangements!

Key Takeaway: A derangement is a permutation with no fixed points—computed via D(n) = n! × Σ((-1)^k/k!) or the recurrence D(n) = (n-1)[D(n-1) + D(n-2)].