Derangements
Lesson · Intermediate
Combinatorics
A derangement is a permutation in which no element is in its original position.
Let Dₙ denote the number of derangements of 1, 2, ..., n.
Suppose the permutation is
For each i, define
A derangement has no fixed points, so
By the Principle of Inclusion–Exclusion,
If k specified elements are fixed, the remaining n − k elements can be permuted in (n − k)! ways. Therefore,
Factoring out n! gives
How many permutations of 1, 2, ..., 8 have exactly two fixed points?
First choose the two elements that remain fixed:
The remaining 6 elements must all move, so they can be arranged in D₆ ways.
Therefore,
Eight people bring eight distinct gifts. The gifts are redistributed so that nobody receives their own gift. In how many distributions do Alice and Bob receive each other's gifts?
Alice's and Bob's assignments are already determined:
Now consider the other 6 people.
None of them may receive their own gift, and the gifts belonging to Alice and Bob are already used.
Therefore, the remaining 6 gifts must form a derangement among the remaining 6 people.
Hence the number is
n ≥ 2
Suppose we want to count derangements of 1, 2, ..., n.
Consider where 1 goes. Since 1 cannot stay fixed, suppose 1 → k for some k ≠ 1.
There are n − 1 choices for k.
Now split into two cases.
Case 1: k → 1
Then 1 and k swap with each other: 1 ↔ k.
The remaining n − 2 elements must form a derangement, giving Dₙ₋₂ possibilities.
Case 2: k ↛ 1
In this case, after fixing 1 → k, the remaining arrangement corresponds to a derangement of n − 1 elements, giving Dₙ₋₁ possibilities.
Therefore, for each of the n − 1 choices of k, there are Dₙ₋₁ + Dₙ₋₂ possibilities.
Hence,
The number of permutations of n elements having exactly r fixed points is
Using the explicit formula
and
Multiply the second equation by n:
Now compare this with Dₙ. The only extra term in Dₙ is
Therefore,