Derangements

A derangement is a permutation of $n$ elements where no element remains in its original position. The number of derangements $D_n$ satisfies: $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$ For large $n$, $D_n \approx \frac{n!}{e}$. Intuition: Start with the inclusion-exclusion principle. Let $A_i$ be the set of permutations where element $i$ is fixed. Then $D_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$. By inclusion-exclusion, this gives the alternating sum above. When to use: Problems asking "how many ways can $n$ items be rearranged so that none is in its original position?" — secret Santa problems, misdelivered letters, hat-check problems. Alternative approach: You can always derive $D_n$ from scratch using inclusion-exclusion on the full permutation set. The formula is a shortcut. First few values: $D_1 = 0,\ D_2 = 1,\ D_3 = 2,\ D_4 = 9,\ D_5 = 44$.