ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# 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:

• φn-1(k) ≠ k, so φn-1 is a derangement of [1,n-1], or
• φn-1(k) = k, and for all xk, φ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 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 AS, 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)).

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.