Derangements

The classic "hat-check problem" asks: $n$ people check their hats, the hats get shuffled randomly, and everyone is handed one hat back — in how many of the $n!$ possible ways of returning the hats does absolutely nobody get their own hat back? Such an arrangement, with no item in its original position, is called a derangement, and the count of derangements of $n$ items, written $D_n$, follows the pattern $D_n = (n-1)\left[D_{n-1} + D_{n-2}\right]$, and for large $n$ the fraction of all $n!$ permutations that are derangements converges quickly to $1/e \approx 0.368$ — meaning roughly 37% of random shuffles leave nobody with their own item back, a number that barely changes once $n$ is more than about 5 or 6.

For example, with $n=4$ hats there are $D_4 = 9$ derangements out of $4! = 24$ total permutations, a ratio of $9/24 = 0.375$ — already close to the limiting $1/e \approx 0.368$ that larger $n$ converges to.

This fast convergence is what makes derangement questions a favorite trick in interviews: candidates often expect the answer to depend heavily on $n$, and are surprised that "what's the probability nobody gets their own item back, for a large group" has essentially the same answer (about 37%) whether the group has 10 people or 10,000.