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[1], en même temps que Nicolas Bernoulli.

Diverses formulations du problèmeModifier

  • Montmort écrit en 1708[1] : « Pierre a un certain nombre de cartes qui ne sont point répétées, et qui sont mêlées à discrétion ; il parie contre Paul que s'il les tire de suite, et qu'il les nomme selon l'ordre des cartes, en commençant, ou par la plus haute, ou par la plus basse, il lui arrivera au moins une fois de tirer celle qu'il nommera. On demande quel est le sort ou l'espérance de Pierre, pour quelque nombre de cartes que ce puisse être, depuis deux jusqu'à treize ».

Il s'agit du jeu appelé à l'époque « jeu du treize ».

  • Leonhard Euler écrit en 1753[2] : « Le jeu de rencontre est un jeu de hasard où des personnes ayant chacune un entier jeu de cartes, en tirent à la fois une carte après l'autre, jusqu'à ce qu'il arrive qu'elles rencontrent la même carte : et alors une des deux personnes gagne. Or, lorsqu'une telle rencontre n'arrive point du tout, alors c'est l'autre des deux personnes qui gagne. Cela posé, on demande la probabilité, que l'une de ces deux personnes aura de gagner. »
  • Pierre Tédenat écrit en 1821[3] : « Quelqu’un tient dans ses mains un paquet de cartes, au nombre de n, portant les nombres 1, 2 , 3 , …… n de la suite naturelle, mêlées au hasard. Il abat, tour à tour, ces cartes sur une table, en prononçant en même temps les mots un, deux, trois, …… dans leur ordre successif ; quelle est la probabilité qu’une fois au moins il lui arrivera, en abattant une carte, de prononcer en même temps le nom du numéro qu’elle porte ? »
  • Eugène Catalan pose le problème en 1837 sous une forme similaire à celle d'Euler, et résout une généralisation[4].
  • Formulation comme problème des chapeaux : « n personnes laissent leur chapeau au vestiaire ; lorsqu'elles viennent les chercher, chacune d'entre elles prend un chapeau au hasard ; quelle est la probabilité qu'aucune d'entre-elles ne porte son chapeau à la sortie ? »

Nous utiliserons cet habillage dans la suite.

Valeurs numériquesModifier

Les dérangements partiels constituent la suite A008290 de l'OEIS. 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  .

  0 1 2 3 4 5 6 7 8
0 1
1 0 1
2 1 0 1
3 2 3 0 1
4 9 8 6 0 1
5 44 45 20 10 0 1
6 265 264 135 40 15 0 1
7 1854 1855 924 315 70 21 0 1
8 14833 14832 7420 2464 630 112 28 0 1

Premier calcul utilisant la formule de PoincaréModifier

La formule de Poincaré :   donne la réponse, en prenant pour   l'évènement : « le i-ème chapeau est à sa place ».

En effet[5]   est l'évènement (contraire de celui cherché) : « l'un des chapeaux est à sa place », et   vaut évidemment   de sorte que  .

Et la probabilité qu'aucun chapeau ne soit à sa place vaut donc  .

Cette probabilité tend très rapidement et de manière alternée vers 1/e. À partir de n = 3 il y a donc en gros une chance sur trois qu'aucun chapeau ne soit à sa place. Et Pierre a raison de parier contre Paul qu'il y aura au moins une coïncidence.

Notion de sous-factorielleModifier

Le nombre de dérangements de n objets vaut donc    désigne l'entier le plus proche de x. Ce nombre   est appelé sous-factorielle de n et noté !n.


Les premières valeurs de   sont :  , suite A000166 de l'OEIS.

On peut exprimer ce nombre sous forme intégrale :  .

Par changement de variable, on obtient la formule exacte :  .


Deuxième calcul par résolution d'un système triangulaireModifier

On remarque que toute permutation de n objets ayant k points fixes est fabriquée à partir d'un dérangement sur le complémentaire de l'ensemble de ses points fixes ; comme il y a   façons de choisir cet ensemble, on obtient :

 .

On peut donc écrire le système linéaire en   :   pour p = 0, 1, … , n dont la matrice dite « de Pascal » s'inverse classiquement et donne

  ;

on retrouve bien la valeur ci-dessus.

Variante utilisant la fonction génératrice   : la relation   permet d'obtenir par produit des séries   ; et partant de   on obtient inversement la valeur attendue  .

Troisième calcul par relation de récurrenceModifier

La formule (1) ci-dessus donne une relation de récurrence forte :  , soit

 .

Mais un raisonnement combinatoire permet d'obtenir la relation de récurrence double :  , dont on déduit la relation de récurrence simple :

 , soit  

qui conduit directement à la formule donnant  .

Démonstration de la relation de récurrence doubleModifier

Supposons que les n personnes sont numérotées de 1 à n ainsi que les n chapeaux.

Nous devons trouver le nombre de configurations où personne ne prend le chapeau ayant même numéro que le sien. Supposons que la première personne prenne le chapeau i. Il y a alors deux possibilités :

  1. soit la personne i ne prend pas le chapeau 1. Ce cas est équivalent à résoudre le problème avec les   personnes et   chapeaux numérotés de 2 à n ;
  2. soit la personne i prend le chapeau 1. Ce cas est équivalent à résoudre le problème avec les   personnes et   chapeaux restants.

Comme il y a   possibilités pour i, on obtient  .

Démonstration du passage à la récurrence simpleModifier

En posant  , la relation   s'écrit   ;

donc  , d'où  .

Quatrième calcul à l'aide des dérangements partielsModifier

Soit[6]   le nombre de configurations où les k premières personnes ne portent pas leur chapeau (ou le nombre de permutations dont les k premiers éléments ne sont pas fixes) ; on a donc   et  .

Parmi ces   configurations, distinguons deux catégories : celle où k + 1 n'a pas son chapeau, qui contient   configurations ; et celle où k + 1 a son propre chapeau, qui en contient  .

On en déduit  , puis  .

La suite   est donc image de la suite   par l'opérateur aux différences finies  .

On en déduit  .

Et de nouveau  .

Application à la loi, l'espérance et la variance du nombre de points fixes d'une permutationModifier

Soit X la variable aléatoire donnant le nombre de personnes portant leur propre chapeau (ou le nombre de points fixes d'une permutation aléatoire de n objets).

Si  , il y a   façons de choisir cet ensemble de points fixes, donc   et bien sûr,  .

Notons que pour n grand devant k,   et X suit donc approximativement une loi de Poisson de paramètre  .

Pour obtenir l'espérance et la variance de X, il est beaucoup plus rapide de remarquer que X est la somme des  ,   étant égal à   si la i-ème personne porte son chapeau,   sinon.

La variable   suit une loi de Bernoulli de paramètre 1/n, donc   : il y a en moyenne une seule personne qui porte son propre chapeau.

Pour la variance, un calcul donne :  [7].

Généralisation : problème des rencontres avec objets typésModifier

On suppose[6] que les n chapeaux sont de p types différents :   du type 1, ...,  du type p ( ) et qu'il y a p catégories parmi les personnes :   de catégorie 1, ...,  de catégorie p (  ; il peut y avoir des personnes sans catégorie) ; il y a rencontre si une personne d'une certaine catégorie prend un chapeau d'un type ayant le même numéro : quelle est la probabilité qu'il n'y ait pas de rencontre ?

La réponse sous forme intégrale est  .

La probabilité qu'une personne prenne un chapeau de type i valant  , l'espérance du nombre de rencontres vaut  .

Le problème simple est obtenu lorsque les   sont égaux à   où l'on retrouve   et une espérance de 1.

Le problème suivant : « Montrant successivement les cartes d'un jeu de 52 cartes, et annonçant, avant de les regarder : As, Roi, Dame, etc., quelle probabilité ai-je que toutes ces annonces soient fausses ? » revient au cas où   et donne une probabilité de   et une espérance du nombre de rencontres de 4 ; pour un jeu de 32 cartes, on trouve une probabilité d'environ   et toujours une espérance de 4.

Voir aussiModifier

Liens externesModifier

Notes et référencesModifier

  1. a et b Pierre Rémond de Montmort, Essay d'analyse sur les jeux de hazard, Paris, (lire en ligne), p. 54, Pierre Rémond de Montmort, Essay d'analyse sur les jeux de hazard, Paris, (lire en ligne), p. 130.
  2. Euler, « Calcul de la probabilité dans le jeu de rencontre », Mémoires de l'Académie des sciences de Berlin, vol. 7,‎ , p. 255-270 (présentation en ligne, lire en ligne) (présenté en 1751).
  3. Tédenat, « Solution du problème des rencontres », Annales de Gergonne, vol. 12,‎ 1821-1822, p. 120-134 (lire en ligne).
  4. E. Catalan, « Solution d'un problème de probabilité relatif au jeu de rencontre », JMPA, 1re série, vol. 2,‎ , p. 469-482 (lire en ligne).
  5. Louis Comtet, Analyse combinatoire, t. 2, Paris, PUF, , p. 9 à 12 et 32.
  6. a et b J. Moreau de Saint-Martin, « Le problème des rencontres », Quadrature, vol. 61,‎ , p. 14-19.
  7. Calcul sur mathcpge.org.