Namespaces
Variants
Actions

Montmort matching problem

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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