Derangement

2020 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)