Difference between revisions of "Derangement"
m (Richard Pinch moved page Inversion (in combinatorics) to Derangement: Better translation, see talk page) |
(links) |
||
Line 1: | Line 1: | ||
''derangement'' | ''derangement'' | ||
− | 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 | + | 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: |
<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> | <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 | + | 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: |
<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> | <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> | ||
− | The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i052/i052430/i05243015.png" /> of Latin squares (cf. [[ | + | 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 |
<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/i05243020.png" /></td> </tr></table> |
Revision as of 07:28, 2 December 2016
derangement
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=39874