The hat-check problem: derangements via inclusion-exclusion

n people check their hats and receive one back at random; what’s the probability nobody gets their own hat back? The answer converges to \(1/e\) remarkably quickly.

import math

from mathematicskit.combinatorics import derangement_count

Probability of a total derangement, for increasing n

for n in range(1, 11):
    d_n = derangement_count(n)
    probability = d_n / math.factorial(n)
    print(f"n={n:2d}: D_n={d_n:>10}, P(derangement) = {probability:.6f} (1/e = {1 / math.e:.6f})")

n= 1: D_n=         0, P(derangement) = 0.000000 (1/e = 0.367879)
n= 2: D_n=         1, P(derangement) = 0.500000 (1/e = 0.367879)
n= 3: D_n=         2, P(derangement) = 0.333333 (1/e = 0.367879)
n= 4: D_n=         9, P(derangement) = 0.375000 (1/e = 0.367879)
n= 5: D_n=        44, P(derangement) = 0.366667 (1/e = 0.367879)
n= 6: D_n=       265, P(derangement) = 0.368056 (1/e = 0.367879)
n= 7: D_n=      1854, P(derangement) = 0.367857 (1/e = 0.367879)
n= 8: D_n=     14833, P(derangement) = 0.367882 (1/e = 0.367879)
n= 9: D_n=    133496, P(derangement) = 0.367879 (1/e = 0.367879)
n=10: D_n=   1334961, P(derangement) = 0.367879 (1/e = 0.367879)