# Derangement

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} \ .$$