Problème des rencontres

En mathématiques, le problème des rencontres, ou problème de Montmort, ou encore problème des chapeaux, consiste à déterminer la probabilité que, n jetons numérotés de 1 à n ayant été mis au hasard dans des cases elles-mêmes numérotées de 1 à n, aucun jeton ne soit à sa place (ou celle de l'évènement contraire). De façon plus savante, c'est la recherche de la probabilité qu'une permutation prise au hasard soit un dérangement, c'est-à-dire ne possède pas de « rencontre », autrement dit de point fixe. Le problème des rencontres a été posé pour la première fois par Pierre Rémond de Montmort en 1708, qui l'a résolu en 1713, en même temps que Nicolas Bernoulli. Montmort écrit en 1708 : . Il s'agit du jeu appelé à l'époque « jeu du treize ». Leonhard Euler écrit en 1753 : Pierre Tédenat écrit en 1821 : Eugène Catalan pose le problème en 1837 sous une forme similaire à celle d'Euler, et résout une généralisation. Formulation comme problème des chapeaux : Nous utiliserons cet habillage dans la suite. Depuis Édouard Lucas, on figure une permutation par une position saturée de tours sur un échiquier n×n (n tours dont aucune n'est en prise avec une autre) ; il s'agit de calculer la proportion de positions saturées n'ayant aucune tour sur une diagonale donnée. De façon équivalente, on peut considérer des grilles de mots croisés à une seule case noire par ligne et par colonne, ou des matrices à un seul par ligne et par colonne, et des ailleurs. Les dérangements partiels constituent la . La ligne correspond au nombre d'éléments impliqués (le nombre de cartes au jeu du treize, le nombre de propriétaires de chapeaux, ou le nombre de tours sur l'échiquier d'Édouard Lucas). La ligne correspond à l'échiquier classique ; la ligne correspondrait au jeu modélisé par Pierre de Montfort, mais qu'il a renoncé à calculer et publier : l'approximation suffit. La colonne correspond au nombre d'éléments à leur place : la permutation considérée est un dérangement pour . La formule de Poincaré : donne la réponse, en prenant pour l'évènement : « le i-ème chapeau est à sa place ».