Derangement

2010 Mathematics Subject Classification: Primary: 05A15 [MSN][ZBL]

A permutation of $n$ elements in which the element $i$ cannot occupy the $i$-th position, $i=1,\ldots,n$: a permutation with no fixed points. The problem of calculating the number $D_n$ of derangements is known as the "Montmort matching problem" or "problème des rencontres" (cf. Classical combinatorial problems). The following formula holds: $$D_n = n! \left({ 1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} }\right) \ .$$ For large $n$ the proportion of permutations which are derangements is thus $$\frac{D_n}{n!} \sim e^{-1} \ .$$

Derangements are a special case of permutations satisfying a specific restriction on the position of the permuted elements. For example, the "problème des ménages" consists in calculating the number $U_n$ of permutations conflicting with the two permutations $(1,2,\ldots,n)$ and $(n,1,\ldots,n-1)$. (Two permutations of $n$ elements are called conflicting if the $i$-th element occupies different positions in each of them for all $i=1,\ldots,n$). The number $U_n$ is given by the formula: $$U_n = \sum_{k=0}^n \frac{2n}{2n-k} \binom{2n-k}{n} (n-k)! \ .$$

The number $L(r,n)$ of Latin rectangles of size $r \times n$ for $r=2,3$ can be calculated in terms of $D_n$ and $U_n$ by the formulas $$L(2,n) = n! \, D_n \ ;$$ $$L(3,n) = \sum_{k=0}^{[n/2]} \binom{n}{k} D_{n-k} U_{n-2k} \ .$$

References

 [1] H.J. Ryser, "Combinatorial mathematics" , Carus Math. Monogr. , 14 , Wiley & Math. Assoc. Amer. (1963) [2] J. Riordan, "An introduction to combinatorial mathematics" , Wiley (1958)
How to Cite This Entry:
Derangement. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Derangement&oldid=39895
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article