Dérangement

Dérangement is a concept in combinatorics describing a permutation of a finite set in which no element remains in its original position. If the set has n elements, a dérangement is a permutation π of {1, …, n} such that π(i) ≠ i for all i.

The number of dérangements of n elements is denoted !n (also d_n). It can be computed by inclusion-exclusion: !n = n! ∑_{k=0}^n (-1)^k / k!. Equivalently, !n satisfies the recurrence !n = (n−1)(!n−1 + !n−2) with initial values !0 = 1 and !1 = 0. This yields small values such as !2 = 1, !3 = 2, !4 = 9, !5 = 44, and so on.

A common asymptotic description is !n ~ n!/e, meaning the proportion of dérangements among all permutations tends to 1/e ≈ 0.3679 as n grows. The exponential generating function for the sequence !n is ∑_{n≥0} !n x^n / n! = e^{−x} / (1 − x).

The classic context is known in French as the problème des rencontres, the problem of encounters, which studies the likelihood and counting of permutations with no fixed points. A well-known probabilistic interpretation is the hat-check problem: if n people randomly return hats, the probability that nobody receives their own hat approaches 1/e as n becomes large.

Dérangements have applications in combinatorics, probability, and computer science, illustrating the use of inclusion-exclusion and derangement-like counting in problems about matching and fixed points.