Main Page | See live article | Alphabetical index

Derangement

In combinatorics, a derangement is a permutation φ of a set S (i.e., a bijection from S into itself) 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:

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 dn as the number of derangements of n letters, and we define d0 = 1, d1 = 0; then dn satisfies the recurrence:

dn = (n-1)(dn-1 + dn-2)

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

limn→∞ dn = n! / e

and the probability pn = dn/n! that a randomly selected permutation is a derangement is

limn→∞ pn = 1/e ~ 0.3679

and in fact, 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