Derangement

In combinatorics, a derangement is a permutation φ of a set S (i.e., a bijection from S into itself) with no fixed points, i.e., for all x in S, φ(x) ≠ x. A frequent problem is to count the number of derangements as a function of n = |S|, often with additional constraints.

Derangements arise in a number of guises in combinatorial problems. For example, each solution to the rooks problem, where n rooks must be placed on an n x n chessboard such that no two rooks occupy the same row or column, can be considered as a derangement of n elements. Another version of the problem arises when we ask for the number of ways n letters, each addressed to a different person, can be placed in n pre-addressed envelopes so that no letter appears in the correctly addressed envelope.

One approach to counting the derangements of n elements is to use induction. First, note that if φ_n is any derangement of the natural numbers [1,n], then for some k in [1,n-1], φ_n(n) = k. Then if we let (k,n) be the permutation of [1,n] which swaps k and n, and we let φ_n−1 be the composition ((k,n) o φ_n); then φ_n−1(n) = n, and either:

• φ_n−1(k) ≠ k, so φ_n−1 is a derangement of [1,n−1], or
• φ_n−1(k) = k, and for all x ≠ k, φ_n−1(x) ≠ x.

In the latter case, φ_n−1 is then a derangement of the set [1, n−1] excluding k; i.e., the composition φ_n−2 = ((k,n−1) o φ_n−1 o (k,n−1)) is a derangement of [1,n−2].

As examples of these two cases, consider the following two derangements of 6 elements as we perform the above described swaps:

      514623 -> (51432)6; and
      315624 -> (31542)6 -> (3142)56

The above described correspondences are 1-to-1. The converse is also true; there are exactly (n-1) ways of converting any derangement of n-1 elements into a derangement of n elements, and (n-1) ways of converting any derangement of n-2 elements into a derangement of n elements. For example, if n = 6 and k = 4, we can perform the following conversions of derangements of length 5 and 4, respectively

      51432 -> 514326 -> 514623; and
      3142  -> 31542  -> 315426 -> 315624

Thus, if we write d_n as the number of derangements of n letters, and we define d₀ = 1, d₁ = 0; then d_n satisfies the recurrence:

d_n = (n − 1)(d_n−1 + d_n−2)

Using this recurrence, it can be shown that, in the limit,

lim_n→∞ d_n/n! = 1 / e ~ 0.3679 ...

This is the limit of the probability p_n = d_n/n! that a randomly selected permutation is a derangement. The probability approaches this limit quite quickly.

Perhaps a more well-known method of counting derangements uses the inclusion-exclusion principle.

Generalizations

Derangements are an example of the wider field of constrained permutations. For example, the ménage problem asks if n married couples are seated boy-girl-boy-girl-... around a circular table, how many ways can they be seated so that no man is seated next to his wife?

More formally, given sets A and S, and some sets U and V of surjections A → S, we often wish to know the number of pairs of functions (f,g) such that f is in U and g is in V, and for all a in A, f(a) ≠ g(a); in other words, where for each f and g, there exists a derangement φ of S such that f(a) = φ(g(a)).

External links

• Sloan's Integer Sequence A000166 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000166)
• Non-sexist solution of the ménage problem (http://hilbert.dartmouth.edu/~doyle/docs/menage/menage/menage.html), Kenneth P. Bogart, Peter G. Doyle