Problème des rencontres

Modèle:Redirect 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ème

Montmort écrit en 1708^[1] : Modèle:Citation.

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

Leonhard Euler écrit en 1753^[2] : Modèle:Citation
Pierre Tédenat écrit en 1821^[3] : Modèle:Citation
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 : Modèle:Citation

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 $1$ par ligne et par colonne, et des $0$ ailleurs.

Valeurs numériques

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

$_{n} ╲^{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

Premier calcul utilisant la formule de Poincaré

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

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

Et la probabilité qu'aucun chapeau ne soit à sa place vaut donc $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 (nombre)|Modèle:Math]]. À 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.

Notion de sous-factorielle

Modèle:Article détaillé Le nombre de dérangements de Modèle:Mvar objets vaut donc $d_{n} = n! p_{n} = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!} = ⌊ \frac{n!}{e} ⌉$ où $⌊ x ⌉$ désigne l'entier le plus proche de Modèle:Mvar. Ce nombre $d_{n}$ est appelé [[Analogues de la factorielle#Sous-factorielle|sous-factorielle de Modèle:Mvar]] et noté !Modèle:Mvar.

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

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

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

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

On remarque que toute permutation de Modèle:Mvar objets ayant Modèle:Mvar 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 $(\binom{n}{k})$ façons de choisir cet ensemble, on obtient :

n! = \sum_{k = 0}^{n} (\binom{n}{k}) d_{k} (1)

.

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

d_{p} = \sum_{k = 0}^{p} (- 1)^{p - k} (\binom{p}{k}) k! = \sum_{k = 0}^{p} (- 1)^{k} (\binom{p}{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 $f (x) = \sum_{n = 0}^{\infty} p_{n} x^{n} = \sum_{n = 0}^{\infty} \frac{d_{n}}{n!} x^{n}$ : la relation $n! = \sum_{k = 0}^{n} (\binom{n}{k}) d_{k}$ permet d'obtenir par produit des séries $e^{x} f (x) = \frac{1}{1 - x}$ ; et partant de $f (x) = e^{- x} . \frac{1}{1 - x}$ on obtient inversement la valeur attendue $p_{n} = \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$ .

Troisième calcul par relation de récurrence

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

p_{n} = 1 - \sum_{k = 0}^{n - 1} \frac{p_{k}}{(n - k)!} = 1 - (\frac{p_{0}}{n!} + \frac{p_{1}}{(n - 1)!} + . . . + \frac{p_{n - 1}}{1!})

.

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

d_{n} = n d_{n - 1} + (- 1)^{n}

, soit

p_{n} = p_{n - 1} + \frac{(- 1)^{n}}{n!}

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

Démonstration de la relation de récurrence double

Supposons que les Modèle:Mvar personnes sont numérotées de 1 à Modèle:Mvar ainsi que les Modèle:Mvar 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 :

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

Comme il y a $n - 1$ possibilités pour i, on obtient $d_{n} = (n - 1) (d_{n - 1} + d_{n - 2})$ .

Démonstration du passage à la récurrence simple

En posant $u_{n} = d_{n} - n d_{n - 1}$ , la relation $d_{n} = (n - 1) (d_{n - 1} + d_{n - 2})$ s'écrit $u_{n} = - u_{n - 1}$ ;

donc $u_{n} = (- 1)^{n - 2} u_{2} = (- 1)^{n}$ , d'où $d_{n} = n d_{n - 1} + (- 1)^{n}$ .

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

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

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

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

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

On en déduit $d_{n, k} = Δ^{k} (n!) = \sum_{q = 0}^{k} (- 1)^{q} (\binom{k}{q}) (n - q)!$ .

Et de nouveau $d_{n} = Δ^{n} (n!) = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) (n - k)! = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$ .

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

Modèle:Article détaillé 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 $X = k$ , il y a $(\binom{n}{k})$ façons de choisir cet ensemble de points fixes, donc $P (X = k) = \frac{(\binom{n}{k})}{n!} d_{n - k} = \frac{1}{k!} \sum_{q = 0}^{n - k} \frac{(- 1)^{q}}{q!}$ et bien sûr, $P (X = 0) = p_{n} = \frac{d_{n}}{n!}$ .

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

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

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

Pour la variance, un calcul donne : $V (X) = 1$ ^[7].

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

On suppose^[6] que les Modèle:Mvar chapeaux sont de p types différents : $n_{1}$ du type 1, ..., $n_{p}$ du type p ( $n = n_{1} + . . + n_{p}$ ) et qu'il y a p catégories parmi les personnes : $m_{1}$ de catégorie 1, ..., $m_{p}$ de catégorie p ( $n ⩾ 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 $\int_{0}^{+ \infty} \frac{e^{- t}}{n!} \prod_{i = 1}^{p} (\sum_{k = 0}^{\min (n_{i}, m_{i})} {(- 1)}^{k} k! (\binom{n_{i}}{k}) (\binom{m_{i}}{k}) t^{n - k}) d t$ .

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

Le problème simple est obtenu lorsque les $n_{i}$ sont égaux à $1$ où l'on retrouve $\int_{0}^{+ \infty} \frac{e^{- t}}{n!} (t - 1)^{n} d t$ et une espérance de 1.

Le problème suivant : Modèle:Citation revient au cas où $n = 52, p = 13, n_{i} = m_{i} = 4$ et donne une probabilité de $\int_{0}^{+ \infty} \frac{e^{- t}}{52!} (t^{4} - 16 t^{3} + 72 t^{2} - 96 t + 24)^{13} 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 $13, 5 %$ et toujours une espérance de 4.

Voir aussi

Applications du principe d'inclusion-exclusion

Liens externes

Analyse du texte de Montmort
$d_{n} = A 000166 (n)$ : Modèle:OEIS
$d_{n, k} = A 047920 (n, k)$ : Modèle:OEIS
$n! P (X = k) = A 008290 (n, k)$ : Modèle:OEIS
Modèle:En Derangmeent numbers sur le site de l'OEIS

Notes et références

Modèle:Références

Modèle:Portail

↑ ^1,0 et ^1,1 Modèle:Ouvrage, Modèle:Ouvrage.
↑ Modèle:Article (présenté en 1751).
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Ouvrage.
↑ ^6,0 ^6,1 et ^6,2 Modèle:Article.
↑ Calcul sur mathcpge.org.

[:0-1] 1,0 et ^1,1 Modèle:Ouvrage, Modèle:Ouvrage.

[2] Modèle:Article (présenté en 1751).

[3] Modèle:Article.

[4] Modèle:Article.

[5] Modèle:Ouvrage.

[:1-6] 6,0 ^6,1 et ^6,2 Modèle:Article.

[7] Calcul sur mathcpge.org.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Problème des rencontres

Sommaire

Diverses formulations du problème

Valeurs numériques

Premier calcul utilisant la formule de Poincaré

Notion de sous-factorielle

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

Troisième calcul par relation de récurrence

Démonstration de la relation de récurrence double

Démonstration du passage à la récurrence simple

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

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

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

Voir aussi

Liens externes

Notes et références

Menu de navigation

Problème des rencontres

Diverses formulations du problème

Valeurs numériques

Premier calcul utilisant la formule de Poincaré

Notion de sous-factorielle

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

Troisième calcul par relation de récurrence

Démonstration de la relation de récurrence double

Démonstration du passage à la récurrence simple

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

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

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

Voir aussi

Liens externes

Notes et références

Menu de navigation

Rechercher