Mathematics.

enumerative combinatorics

Derangements

Combinatorics30 minDifficulty3 out of 10

You should know: permutations, inclusion exclusion principle

Overview

A derangement is a permutation of a set in which no element appears in its original position — a 'complete shuffle' with no fixed points. The number of derangements of n objects is denoted !n (the subfactorial), and it is a classic application of the inclusion-exclusion principle. Derangements answer questions like the 'hat-check problem': if n people check their hats and the hats are returned at random, in how many ways can every person get someone else's hat.

Intuition

Derangements come directly from applying inclusion-exclusion to the 'bad' events A_i = 'element i is in its original position.' The total number of permutations with at least one fixed point is found by inclusion-exclusion on these n events, and subtracting that from n! (all permutations) leaves exactly the derangements. Because each term in the inclusion-exclusion sum contributes a 1/k! factor, the formula !n = n!∑(-1)^k/k! emerges — and as n grows, this ratio converges to 1/e, so roughly 37% of random permutations are complete derangements no matter how large n is.

Formal Definition

Definition

The number of derangements of an n-element set is given by inclusion-exclusion over the events 'element i is fixed':

!n=n!∑k=0n(−1)kk!!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}
Derangement formula
!n=(n−1)(!(n−1)+!(n−2))!n = (n-1)\big(!(n-1) + !(n-2)\big)
Recurrence relation
lim⁡n→∞!nn!=1e\lim_{n\to\infty} \frac{!n}{n!} = \frac{1}{e}
Asymptotic probability of a derangement

Worked Examples

  1. List all 3! = 6 permutations and mark which have no fixed points.

    (2,3,1) and (3,1,2) have no fixed points(2,3,1) \text{ and } (3,1,2) \text{ have no fixed points}

  2. Confirm with the formula.

    !3=3!(10!−11!+12!−13!)=6(1−1+0.5−16)=6⋅13=2!3 = 3!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}\right) = 6\left(1-1+0.5-\tfrac{1}{6}\right) = 6\cdot\tfrac{1}{3} = 2

Answer: !3 = 2 derangements: (2,3,1) and (3,1,2).

Practice Problems

Difficulty 3/10

Using the recurrence !n = (n-1)(!(n-1)+!(n-2)) with !1=0 and !2=1, find !3.

Difficulty 4/10

Using the recurrence, find !5 given !3=2 and !4=9.

Difficulty 5/10

5 friends check their coats. In how many ways can the coats be returned so that no one gets their own coat back?

Quiz

A derangement is a permutation in which:
What is !4?
As n grows large, the probability that a random permutation is a derangement approaches:

Summary

  • A derangement is a permutation with no fixed points; !n counts derangements of n objects.
  • !n is derived via inclusion-exclusion on the events 'element i is fixed', giving !n = n!∑_{k=0}^n (-1)^k/k!.
  • Small values: !1=0, !2=1, !3=2, !4=9, !5=44, and !n/n! → 1/e as n → ∞.

References

  1. WebsiteWikipedia — Derangement