Derangements

Permutations with no fixed point, via inclusion-exclusion and the e^-1 limit.

The idea

A derangement is a reshuffling of $n$ labelled items among $n$ labelled slots that leaves nothing where it started. Recall that a permutation of $\{1, \dots, n\}$ assigns to each position one of the items, every item used exactly once, and that a position is a fixed point when the item sitting there is the one that belongs there.

Definition (Derangement).

A derangement of $\{1, \dots, n\}$ is a permutation with no fixed point. The number of derangements among the $n!$ permutations of $n$ items is written $D_n$.

The object being counted is the finished assignment — which item ended in which position. Two shuffles are the same derangement exactly when every item lands in the same place; how the shuffling was carried out is not part of the object.

Counting derangements directly is awkward, because "no fixed point" is a condition on all $n$ positions at once. The first few values are $D_1 = 0$, $D_2 = 1$, $D_3 = 2$ and $D_4 = 9$.

Ways to work on it

• Walkthrough. Derive D_n from inclusion-exclusion, and see why D_n/n! approaches e^-1.
• Proof. Derive the recurrence D_n = (n-1)(D_n-1+D_n-2) by following where element 1 goes.
• Practice. Count the outcomes with exactly m fixed points.
• Hardest. A partial derangement — only some positions are forbidden, so the formula does not apply.

Not sure where to start? Take the ten-question placement test.