Difference between revisions of "Derangement"
m (typo) |
(MSC 05A15) |
||
| Line 1: | Line 1: | ||
| − | + | {{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 <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: | ||
Revision as of 07:32, 2 December 2016
2020 Mathematics Subject Classification: Primary: 05A15 [MSN][ZBL]
A permutation of 
elements in which the element 
cannot occupy the 
-th position, 
. The problem of calculating the number 
of derangements is known as the "Montmort matching problem" or "problème des rencontres" (cf. Classical combinatorial problems). The following formula holds:
 |
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 
of permutations conflicting with the two permutations 
and 
. (Two permutations of 
elements are called conflicting if the 
-th element occupies different positions in each of them for all 
). The number 
is given by the formula:
 |
The number 
of Latin squares (cf. Latin square) of size 
for 
can be calculated in terms of 
and 
by the formulas
 |
 |
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) |
Derangement. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Derangement&oldid=39882