Namespaces
Variants
Actions

Difference between revisions of "Montmort matching problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(MSC|01A50|60-03)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
''derangement problem''
+
{{TEX|done}}{{MSC|01A50|60-03}}
  
Take two sets, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202201.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202202.png" />, and a [[Bijection|bijection]], <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202203.png" />, between them. (E.g., take <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202204.png" /> married couples and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202205.png" /> be the set of husbands and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202206.png" /> the set of wives.) Now, take a random paring (a bijection again). What is the chance that this random pairing gives at least one  "correct match"  (i.e. coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202207.png" /> in at least one element). Asymptotically, this [[Probability|probability]] is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202208.png" />. This follows immediately from the formula given in [[Classical combinatorial problems|Classical combinatorial problems]] for the number of permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m1202209.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m12022010.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120220/m12022011.png" />.
+
''derangement problem'', ''problème des rencontres''
  
This problem was considered first by P.R. de Montmort (around 1700) in connection with a card game known as the  "jeu du treize" ,  "jeu de rencontre"  or simply  "rencontre" .
+
Take two sets, $A$ and $B$, and a [[bijection]], $\phi$, between them. (E.g., take $n$ married couples and let $A$ be the set of husbands and $B$ the set of wives.) Now, take a random pairing (a bijection again). What is the chance that this random pairing gives at least one  "correct match"  (i.e. coincides with $\phi$ in at least one element). Asymptotically, this [[probability]] is $1-e^{-1}$. This follows immediately from the formula given in [[Classical combinatorial problems]] for the number of ''[[derangement]]s'': permutations $\pi$ such that $\pi(i)\neq i$ for all $i=1,\ldots,n$.
 +
 
 +
This problem was considered first by [[Montmort, Pierre Rémond de|P.R. de Montmort]] (around 1700) in connection with a card game known as the  "jeu du treize",  "jeu de rencontre"  or simply  "rencontre".
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Knobloch,  "Euler and the history of a problem in probability theory"  ''Ganita–Bharati'' , '''6'''  (1984)  pp. 1–12</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Knobloch,  "Euler and the history of a problem in probability theory"  ''Ganita–Bharati'' , '''6'''  (1984)  pp. 1–12</TD></TR></table>

Latest revision as of 07:34, 2 December 2016

2020 Mathematics Subject Classification: Primary: 01A50 Secondary: 60-03 [MSN][ZBL]

derangement problem, problème des rencontres

Take two sets, $A$ and $B$, and a bijection, $\phi$, between them. (E.g., take $n$ married couples and let $A$ be the set of husbands and $B$ the set of wives.) Now, take a random pairing (a bijection again). What is the chance that this random pairing gives at least one "correct match" (i.e. coincides with $\phi$ in at least one element). Asymptotically, this probability is $1-e^{-1}$. This follows immediately from the formula given in Classical combinatorial problems for the number of derangements: permutations $\pi$ such that $\pi(i)\neq i$ for all $i=1,\ldots,n$.

This problem was considered first by P.R. de Montmort (around 1700) in connection with a card game known as the "jeu du treize", "jeu de rencontre" or simply "rencontre".

References

[a1] E. Knobloch, "Euler and the history of a problem in probability theory" Ganita–Bharati , 6 (1984) pp. 1–12
How to Cite This Entry:
Montmort matching problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Montmort_matching_problem&oldid=14268
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article