Derangement

A derangement is a permutation of a finite set in which no element appears in its original position. If a set has n elements, a derangement is a permutation π of {1, ..., n} such that π(i) ≠ i for every i. Derangements are often denoted by !n or Dn.

For example, when n = 3, the derangements are 231 and 312. For n = 4, there are 9 derangements. In general, the number of derangements grows rapidly with n.

Counting and formulas: The number of derangements of n elements, !n, can be computed as !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. A common approximation is !n ≈ ⌊n!/e + 1/2⌋, and the exact value is given by the alternating sum above.

Asymptotics and probability: As n grows, the probability that a randomly chosen permutation of n elements is a derangement approaches 1/e ≈ 0.3679. Consequently, !n is asymptotically n!/e.

History and related concepts: Derangements are central to the hat check problem, attributed to Montmort in the early 18th century, and later analyzed by Lucas and others. They are related to the broader study of fixed points and to rencontres numbers, which count permutations by the number of fixed points.