Derangement

In combinatorics, a derangement is a permutation φ of a set S with the property that 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 derangment 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! / e

and the probability p_n = d_n/n! that a randomly selected permutation is a derangement is

lim_n→∞ p_n = 1/e ~ 0.3679

and in fact, the probability approaches this limit quite quickly.

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), Kenneth P. Bogart, Peter G. Doyle