Namespaces
Variants
Actions

Difference between revisions of "Derangement"

From Encyclopedia of Mathematics
Jump to: navigation, search
(MSC 05A15)
(Tex done)
Line 1: Line 1:
{{MSC|05A15}}
+
{{TEX|done}}{{MSC|05A15}}
  
A permutation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524301.png" /> elements in which the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524302.png" /> cannot occupy the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524303.png" />-th position, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524304.png" />. The problem of calculating the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524305.png" /> of derangements is known as the "[[Montmort matching problem]]" or "problème des rencontres"  (cf. [[Classical combinatorial problems]]). The following formula holds:
+
A permutation of $n$ elements in which the element $i$ cannot occupy the $i$-th position, $i=1,\ldots,n$. 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) \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524306.png" /></td> </tr></table>
+
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)! \ .
 +
$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524307.png" /> of permutations conflicting with the two permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524308.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i0524309.png" />. (Two permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243010.png" /> elements are called conflicting if the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243011.png" />-th element occupies different positions in each of them for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243012.png" />). The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243013.png" /> is given by the formula:
+
The number $L(r,n)$ of [[Latin square]]s of size $r \times n$ for $r=2,3$ can be calculated in terms of $D_n$ and $U_n$ by the formulas
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243014.png" /></td> </tr></table>
+
L(2,n) = n! \, D_n \ ;
 
+
$$
The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243015.png" /> of Latin squares (cf. [[Latin square]]) of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243016.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243017.png" /> can be calculated in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243019.png" /> by the formulas
+
$$
 
+
L(3,n) = \sum_{k=0}^{[n/2]} \binom{n}{k} D_{n-k} U_{n-2k} \ .
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243020.png" /></td> </tr></table>
+
$$
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243021.png" /></td> </tr></table>
 
  
 
====References====
 
====References====

Revision as of 08:01, 3 December 2016

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

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 squares 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=39883
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article