Counting and combinatorics

Derangements

Counts the permutations that fix nothing — the hat-check problem and its many disguises.

D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \ \longrightarrow\ \frac{n!}{e}

Where

$D_n/n! \to 1/e$: About $36.8\%$ , and essentially exact from $n = 5$ .

Assumptions

Derived by inclusion–exclusion over which items are fixed.

Sanity check. $D_5 = 44$ out of $120$ , which is $36.7\%$ — already within $0.002$ of the limit.

Where this is taught

Inclusion–exclusion, derangements and the pigeonhole · COMB · Inclusion–exclusion and invariants