View source for Derangement

{{TEX|done}}{{MSC|05A15}}

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 rectangle]]s 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====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  H.J. Ryser,   "Combinatorial mathematics" , ''Carus Math. Monogr.'' , '''14''' , Wiley &amp; Math. Assoc. Amer.  (1963)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,   "An introduction to combinatorial mathematics" , Wiley  (1958)</TD></TR>
</table>