Problème des rencontres

• 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.

• 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 ${\displaystyle 1}$ par ligne et par colonne, et des ${\displaystyle 0}$ ailleurs.

Les dérangements partiels constituent la suite A008290 de l'OEIS. La ligne ${\displaystyle n}$ 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 ${\displaystyle n=8}$ correspond à l'échiquier classique ; la ligne ${\displaystyle n=13}$ correspondrait au jeu modélisé par Pierre de Montfort, mais qu'il a renoncé à calculer et publier : l'approximation ${\displaystyle d_{13,0}/13!\approx e^{-1}}$ suffit. La colonne ${\displaystyle k}$ correspond au nombre d'éléments à leur place : la permutation considérée est un dérangement pour ${\displaystyle k=0}$.

${\displaystyle _{n}\!\!\diagdown \!\!^{k}}$	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

La formule de Poincaré : ${\displaystyle P\left(\,\bigcup _{i=1}^{n}A_{i}\,\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n}P(A_{i_{1}}\cap A_{i_{2}}\cap \ldots \cap A_{i_{k}})\right)}$ donne la réponse, en prenant pour ${\displaystyle A_{i}}$ l'évènement : « le i-ème chapeau est à sa place ».

En effet[5] ${\displaystyle \bigcup _{i=1}^{n}A_{i}}$ est l'évènement (contraire de celui cherché) : « l'un des chapeaux est à sa place », et ${\displaystyle P(A_{i_{1}}\cap A_{i_{2}}\cap \ldots \cap A_{i_{k}})}$ vaut évidemment ${\displaystyle (n-k)!/n!}$ de sorte que ${\displaystyle P\left(\,\bigcup _{i=1}^{n}A_{i}\,\right)=\sum _{k=1}^{n}\left((-1)^{k-1}{n \choose k}{\frac {(n-k)!}{n!}}\right)=\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k!}}}$.

Et la probabilité qu'aucun chapeau ne soit à sa place vaut donc ${\displaystyle p_{n}=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$.

Cette probabilité tend très rapidement et de manière alternée vers 1/e. À partir de n = 3 il y a donc environ 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.

Le nombre de dérangements de n objets vaut donc ${\displaystyle d_{n}=n!p_{n}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}=\left\lfloor {\frac {n!}{e}}\right\rceil }$ où ${\displaystyle \left\lfloor x\right\rceil }$ désigne l'entier le plus proche de x. Ce nombre ${\displaystyle d_{n}}$ est appelé sous-factorielle de n et noté !n.

Les premières valeurs de ${\displaystyle d_{n}=!n}$ sont : ${\displaystyle d_{1}=0,d_{2}=1,d_{3}=2,d_{4}=9,d_{5}=44,d_{6}=265,d_{7}=1854,d_{8}=14833}$, suite A000166 de l'OEIS.

En utilisant l'expression intégrale de la factorielle : ${\displaystyle n!=\int _{0}^{+\infty }\mathrm {e} ^{-t}t^{n}\mathrm {d} t}$ , on peut exprimer ce nombre sous forme intégrale : ${\displaystyle d_{n}=n!p_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}(n-k)!=\sum _{k=0}^{n}(-1)^{k}{n \choose k}\int _{0}^{+\infty }\mathrm {e} ^{-t}t^{n-k}\,\mathrm {d} t=\int _{0}^{+\infty }\mathrm {e} ^{-t}(t-1)^{n}\,\mathrm {d} t}$ [6].

Par changement de variable ${\displaystyle u=1-t}$, on obtient la formule exacte : ${\displaystyle p_{n}={\frac {1}{\mathrm {e} }}+{\frac {(-1)^{n}}{\mathrm {e} .n!}}\int _{0}^{1}\mathrm {e} ^{u}u^{n}\,\mathrm {d} u}$ .

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 ${\displaystyle {n \choose k}}$ façons de choisir cet ensemble, on obtient :

${\displaystyle n!=\sum _{k=0}^{n}{n \choose k}d_{k}\qquad (1)}$.

On peut donc écrire le système linéaire en ${\displaystyle d_{0},\dots ,d_{n}}$ : ${\displaystyle p!=\sum _{k=0}^{p}{p \choose k}d_{k}}$ pour p = 0, 1, … , n dont la matrice dite « de Pascal » s'inverse classiquement et donne

${\displaystyle d_{p}=\sum _{k=0}^{p}(-1)^{p-k}{p \choose k}k!=\sum _{k=0}^{p}(-1)^{k}{p \choose k}(p-k)!=p!\sum _{k=0}^{p}{\frac {(-1)^{k}}{k!}}}$ ;

on retrouve bien la valeur ci-dessus.

Variante utilisant la fonction génératrice ${\displaystyle f(x)=\sum _{n=0}^{\infty }p_{n}x^{n}=\sum _{n=0}^{\infty }{\frac {d_{n}}{n!}}x^{n}}$ : la relation ${\displaystyle n!=\sum _{k=0}^{n}{n \choose k}d_{k}}$ permet d'obtenir par produit des séries ${\displaystyle \mathrm {e} ^{x}f(x)={\frac {1}{1-x}}}$ ; et partant de ${\displaystyle f(x)=\mathrm {e} ^{-x}.{\frac {1}{1-x}}}$ on obtient inversement la valeur attendue ${\displaystyle p_{n}=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$.

La formule (1) ci-dessus donne une relation de récurrence forte : ${\displaystyle d_{n}=n!-\sum _{k=0}^{n-1}{n \choose k}d_{k}}$, soit

${\displaystyle p_{n}=1-\sum _{k=0}^{n-1}{\frac {p_{k}}{(n-k)!}}=1-\left({\frac {p_{0}}{n!}}+{\frac {p_{1}}{(n-1)!}}+...+{\frac {p_{n-1}}{1!}}\right)}$.

Mais un raisonnement combinatoire permet d'obtenir la relation de récurrence double : ${\displaystyle d_{n}=(n-1)(d_{n-1}+d_{n-2})}$, dont on déduit la relation de récurrence simple :

${\displaystyle d_{n}=nd_{n-1}+(-1)^{n}}$, soit ${\displaystyle p_{n}=p_{n-1}+{\frac {(-1)^{n}}{n!}}}$

qui conduit directement à la formule donnant ${\displaystyle p_{n}}$.

Soit[6] ${\displaystyle d_{n,k}}$ 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 ${\displaystyle d_{n,0}=n!}$ et ${\displaystyle d_{n,n}=d_{n}}$.

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

On en déduit ${\displaystyle d_{n,k}=d_{n,k+1}+d_{n-1,k}}$, puis ${\displaystyle d_{n,k}=d_{n,k-1}-d_{n-1,k-1}}$.

La suite ${\displaystyle (d_{n,k})_{n}}$ est donc image de la suite ${\displaystyle (d_{n,k-1})_{n}}$ par l'opérateur aux différences finies ${\displaystyle \Delta (u_{n})=u_{n}-u_{n-1}}$.

On en déduit ${\displaystyle d_{n,k}=\Delta ^{k}(n!)=\sum _{q=0}^{k}(-1)^{q}{k \choose q}(n-q)!}$.

Et de nouveau ${\displaystyle d_{n}=\Delta ^{n}(n!)=\sum _{k=0}^{n}(-1)^{k}{n \choose k}(n-k)!=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$.

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 ${\displaystyle X=k}$, il y a ${\displaystyle n \choose k}$ façons de choisir cet ensemble de points fixes, donc ${\displaystyle P(X=k)={\frac {n \choose k}{n!}}d_{n-k}={\frac {1}{k!}}\sum _{q=0}^{n-k}{\frac {(-1)^{q}}{q!}}}$ et bien sûr, ${\displaystyle P(X=0)=p_{n}={\frac {d_{n}}{n!}}}$.

Notons que pour n grand devant k, ${\displaystyle P(X=k)\approx {\frac {1}{\mathrm {e} .k!}}}$ et X suit donc approximativement une loi de Poisson de paramètre ${\displaystyle 1}$.

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

La variable ${\displaystyle X_{i}}$ suit une loi de Bernoulli de paramètre 1/n, donc ${\displaystyle E(X)=1}$ : il y a en moyenne une seule personne qui porte son propre chapeau.

Pour la variance, un calcul donne : ${\displaystyle V(X)=1}$[7].

On suppose[6] que les n chapeaux sont de p types différents : ${\displaystyle n_{1}}$ du type 1, ...,${\displaystyle n_{p}}$ du type p (${\displaystyle n=n_{1}+..+n_{p}}$) et qu'il y a p catégories parmi les personnes : ${\displaystyle m_{1}}$ de catégorie 1, ...,${\displaystyle m_{p}}$ de catégorie p (${\displaystyle n\geqslant m_{1}+..+m_{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 ${\displaystyle \int _{0}^{+\infty }{\frac {\mathrm {e} ^{-t}}{n!}}\prod _{i=1}^{p}\left(\sum _{k=0}^{\min(n_{i},m_{i})}{\left(-1\right)^{k}k!{n_{i} \choose k}{m_{i} \choose k}}t^{n-k}\right)\,\mathrm {d} t}$.

La probabilité qu'une personne prenne un chapeau de type i valant ${\displaystyle n_{i}/n}$, l'espérance du nombre de rencontres vaut ${\displaystyle {\frac {\sum _{i=1}^{p}n_{i}m_{i}}{n}}}$.

Le problème simple est obtenu lorsque les ${\displaystyle n_{i}}$ sont égaux à ${\displaystyle 1}$ où l'on retrouve ${\displaystyle \int _{0}^{+\infty }{\frac {\mathrm {e} ^{-t}}{n!}}(t-1)^{n}\,\mathrm {d} t}$ 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ù ${\displaystyle n=52,p=13,n_{i}=m_{i}=4}$ et donne une probabilité de ${\displaystyle \int _{0}^{+\infty }{\frac {\mathrm {e} ^{-t}}{52!}}(t^{4}-16t^{3}+72t^{2}-96t+24)^{13}\,\mathrm {d} t\approx 1,6\%}$ et une espérance du nombre de rencontres de 4 ; pour un jeu de 32 cartes, on trouve une probabilité d'environ ${\displaystyle 13,5\%}$ et toujours une espérance de 4.

• Applications du principe d'inclusion-exclusion

• Analyse du texte de Montmort
• Suite ${\displaystyle d_{n}=A000166(n)}$ dans l'encyclopédie des suites entières
• Suite ${\displaystyle d_{n,k}=A047920(n,k)}$ dans l'encyclopédie des suites entières
• Suite ${\displaystyle n!P(X=k)=A008290(n,k)}$ dans l'encyclopédie des suites entières
• Article sur les dérangements dans cette même encyclopédie