# Formule du crible/Rencontre du troisième type

Dans ce chapitre, nous allons étudier les rencontres du troisième type que l’on peut modéliser de la façon suivante :
Soit une urne contenant 3n boules. Trois boules portent le numéro 1, trois autres portent le numéro 2, trois autres portent le numéro 3, et ainsi de suite.
À côté de l’urne se trouvent n boîtes numérotées de 1 à n.
On tire les boules sans remise en mettant les trois premières dans la première boîte, les trois suivantes dans la deuxième boîte, et ainsi de suite jusqu'à ce qu’il y ait trois boules par boîte.
On dira qu’il y a une rencontre dans la boîte numéro i si les trois boules de cette boîte portent le même numéro.
Soit A$_i$ l’événement : Il y a une rencontre dans la boîte numéro i.
A$_i$ ∩ A$_j$ est alors l’événement : Il y a une rencontre dans la boîte i et une rencontre dans la boîte j.
A$_i$ ∪ A$_j$ est l’événement : Il y a une rencontre dans au moins une des deux boîtes i ou j.
Soit X$_n$ la variable aléatoire prenant pour valeur le nombre total de rencontres après les n tirages.
On a :
    ${\begin{aligned}p(X_{n}\geq 1)&=p\left(\bigcup _{i=1}^{n}A_{i}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}p\left(\bigcap _{j=1}^{k}A_{i_{j}}\right)\right).\end{aligned}}$
Calculons $p\left(\bigcap _{j=1}^{k}A_{i_{j}}\right)$.
Une boule étant mise dans la boîte numéro i, la probabilité que les deux boules suivantes arrivant dans cette boîte aient le même numéro est :
    $p(A_{i})={\frac {1}{3n-1 \choose 2}}$.
D’après la formule des probabilités composées, on a :
    ${\begin{aligned}p(A_{i}\cap A_{j})&=p(A_{i})\times p(A_{j}/A_{i})\\&={\frac {1}{3n-1 \choose 2}}\times {\frac {1}{3(n-1)-1 \choose 2}}.\end{aligned}}$
Plus généralement, à l’aide de la formule des probabilités composées, on obtient :
    ${\begin{aligned}p\left(\bigcap _{i=1}^{k}A_{i_{j}}\right)&=p\left(A_{i_{1}}\right)\times p\left(A_{i_{2}}/A_{i_{1}}\right)\times p\left(A_{i_{3}}/(A_{i_{1}}\cap A_{i_{2}})\right)\times \cdots \times p\left(A_{i_{k}}/\bigcap _{j=1}^{k-1}A_{i_{j}}\right)\\&={\frac {1}{3n-1 \choose 2}}\times {\frac {1}{3(n-1)-1 \choose 2}}\times {\frac {1}{3(n-2)-1 \choose 2}}\times \cdots \times {\frac {1}{3(n-k+1)-1 \choose 2}}\\&={\frac {2^{k}}{\left((3n-1)(3n-2)\right)\left((3n-4)(3n-5)\right)\cdots \left((3n-3k+2)(3n-3k+1)\right)}}\\&={\frac {3n(3n-3)(3n-6)\cdots (3n-3k+3)\times 2^{k}}{3n(3n-1)(3n-2)(3n-3)\cdots (3n-2k+1)}}\\&={\frac {2^{k}3^{k}A_{n}^{k}}{3n(3n-1)(3n-2)\cdots (3n-3k+1)}}\\&={\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}.\end{aligned}}$
En poursuivant alors le calcul de p(X$_n$ ≥ 1), on obtient :
    ${\begin{aligned}p(X_{n}\geq 1)&=p\left(\bigcup _{i=1}^{n}A_{i}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}p\left(\bigcap _{j=1}^{k}A_{i_{j}}\right)\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}{\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}{\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}\right).\end{aligned}}$
On en déduit :
    ${\begin{aligned}p(X_{n}=0)&=1-p(X_{n}\geq 1)\\&=1-\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}{\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}\right)\\&=1+\sum _{k=1}^{n}\left((-1)^{k}{n \choose k}{\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}\right)\\&=\sum _{k=0}^{n}\left((-1)^{k}{n \choose k}{\frac {6^{k}A_{n}^{k}(3n-3k)!}{(3n)!}}\right)\\&=\sum _{k=0}^{n}\left({\frac {(-6)^{k}n!(3n-3k)!n!}{(3n)!k!(n-k)!(n-k)!}}\right)\\&=\sum _{k=0}^{n}\left({\frac {(-2\times 3)^{k}}{k!}}\times {\frac {\frac {(3n-3k)!}{(n-k)!^{2}}}{\frac {(3n)!}{n!^{2}}}}\right).\end{aligned}}$
Nous venons de calculer la probabilité qu’il n'y ait aucune rencontre.
Calculons maintenant p(X$_n$ = r). Pour cela, il faut :
* choisir les r boîtes où auront lieu les rencontres : ${\binom {n}{r}}$ possibilités ;
* calculer la probabilité qu’il y ait rencontre dans ces r boîtes :
    ${\frac {1}{3n-1 \choose 2}}\times {\frac {1}{3(n-1)-1 \choose 2}}\times {\frac {1}{3(n-2)-1 \choose 2}}\times \cdots \times {\frac {1}{3(n-r+1)-1 \choose 2}}$ ;
* calculer la probabilité qu’il n’y ait pas de rencontre dans les n – r autres boîtes : p(X$_{n–r}$ = 0).
On aura donc :
    ${\begin{aligned}p(X_{n}=r)&={n \choose r}{\frac {1}{3n-1 \choose 2}}\times {\frac {1}{3(n-1)-1 \choose 2}}\times {\frac {1}{3(n-2)-1 \choose 2}}\times \cdots \times {\frac {1}{3(n-r+1)-1 \choose 2}}p(X_{n-r}=0)\\&={n \choose r}{\frac {6^{r}A_{n}^{r}(3n-3r)!}{(3n)!}}p(X_{n-r}=0)\\&={\frac {6^{r}n!(3n-3r)!n!}{(3n)!r!(n-r)!(n-r)!}}p(X_{n-r}=0)\\&={\frac {(2\times 3)^{r}}{r!}}\times {\frac {\frac {(3n-3r)!}{(n-r)!^{2}}}{\frac {(3n)!}{n!^{2}}}}p(X_{n-r}=0)\\&={\frac {(2\times 3)^{r}}{r!}}\times {\frac {\frac {(3n-3r)!}{(n-r)!^{2}}}{\frac {(3n)!}{n!^{2}}}}\times \sum _{k=0}^{n}\left({\frac {(-2\times 3)^{k}}{k!}}\times {\frac {\frac {(3n-3r-3k)!}{(n-r-k)!^{2}}}{\frac {(3n-3r)!}{(n-r)!^{2}}}}\right)\\&={\frac {(3!)^{r}}{r!}}\times {\frac {n!^{2}}{(3n)!}}\times \sum _{k=0}^{n-r}\left({\frac {(-3!)^{k}}{k!}}\times {\frac {(3n-3r-3k)!}{(n-r-k)!^{2}}}\right).\end{aligned}}$
Nous avons donc le théorème suivant :
Soit 3n objets appariés par groupe de trois. La probabilité de r rencontres du troisième type entre ces 3n objets est :
    ${\frac {(3!)^{r}}{r!}}\times {\frac {n!^{2}}{(3n)!}}\times \sum _{k=0}^{n-r}\left({\frac {(-3!)^{k}}{k!}}\times {\frac {(3n-3r-3k)!}{(n-r-k)!^{2}}}\right)$.
| Rencontre du second type | Rencontre du p-ième type |