Difference between revisions of "Montmort matching problem"
m (better) |
(MSC|01A50|60-03) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{TEX|done}} | + | {{TEX|done}}{{MSC|01A50|60-03}} |
| − | |||
| − | + | ''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 |
Montmort matching problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Montmort_matching_problem&oldid=39757