# Formule du crible/Rencontre du second type

Les permutations peuvent se classer dans les rencontres du premier type.
Dans ce chapitre, nous allons étudier les rencontres du second type que l’on peut modéliser de la façon suivante :
Soit une urne contenant 2n boules. Deux boules portent le numéro 1 ; deux autres portent le numéro 2 ; deux 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 deux premières dans la première boîte ; les deux suivantes dans la deuxième boîte. Et ainsi de suite jusqu'à ce qu’il y ait deux boules par boîte.
(Dans une rencontre du premier type, on n'aurait mis qu’une boule par boîte).
On dira qu’il y a une rencontre dans la boîte numéro i si les deux 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$ représentera 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$ représentera 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 de rencontres total après avoir effectué les 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 la seconde boule arrivant dans cette boîte ait le même numéro sera :
$p(A_{i})={\frac {1}{2n-1}}$
D’après la formule des probabilités composées, on aura :
${\begin{aligned}p(A_{i}\cap A_{j})&=p(A_{i})\times p(A_{j}/A_{i})\\&={\frac {1}{2n-1}}\times {\frac {1}{2n-3}}\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}{2n-1}}\times {\frac {1}{2n-3}}\times {\frac {1}{2n-5}}\times \cdots \times {\frac {1}{2n-(2k-1)}}\\&={\frac {1}{(2n-1)(2n-3)(2n-5)\cdots (2n-2k+1)}}\\&={\frac {2n(2n-2)(2n-4)\cdots (2n-2k+2)}{2n(2n-1)(2n-2)\cdots (2n-2k+1)}}\\&={\frac {2^{k}A_{n}^{k}}{2n(2n-1)(2n-2)\cdots (2n-2k+1)}}\\&={\frac {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\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 {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}{\frac {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\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 {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\right)\\&=1+\sum _{k=1}^{n}\left((-1)^{k}{n \choose k}{\frac {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\right)\\&=\sum _{k=0}^{n}\left((-1)^{k}{n \choose k}{\frac {2^{k}A_{n}^{k}(2n-2k)!}{(2n)!}}\right)\\&=\sum _{k=0}^{n}\left({\frac {(-2)^{k}n!(2n-2k)!n!}{(2n)!k!(n-k)!(n-k)!}}\right)\\&=\sum _{k=0}^{n}\left({\frac {(-2)^{k}}{k!}}\times {\frac {2n-2k \choose n-k}{2n \choose n}}\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 : ${n \choose r}$ possibilités ;
* calculer la probabilité qu’il y ait rencontre dans ces r boîtes :
    ${\frac {1}{2n-1}}\times {\frac {1}{2n-3}}\times \cdots \times {\frac {1}{2n-(2r-1)}}$ ;
* 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}{2n-1}}\times {\frac {1}{2n-3}}\times \cdots \times {\frac {1}{2n-(2r-1)}}p(X_{n-r}=0)\\&={n \choose r}{\frac {2^{r}A_{n}^{r}(2n-2r)!}{(2n)!}}p(X_{n-r}=0)\\&={\frac {2^{r}n!(2n-2r)!n!}{(2n)!r!(n-r)!(n-r)!}}p(X_{n-r}=0)\\&={\frac {2^{r}}{r!}}\times {\frac {2n-2r \choose n-r}{2n \choose n}}p(X_{n-r}=0)\\&={\frac {2^{r}}{r!}}\times {\frac {2n-2r \choose n-r}{2n \choose n}}\times \sum _{k=0}^{n-r}\left({\frac {(-2)^{k}}{k!}}\times {\frac {2n-2r-2k \choose n-r-k}{2n-2r \choose n-r}}\right)\\&={\frac {2^{r}}{r!{2n \choose n}}}\times \sum _{k=0}^{n-r}\left({\frac {(-2)^{k}}{k!}}\times {2n-2r-2k \choose n-r-k}\right)\end{aligned}}$
Nous avons donc le théorème suivant :
Soit 2n objets appariés deux à deux. La probabilité de r rencontres du second type entre ces 2n objets est :
    ${\frac {2^{r}}{r!{2n \choose n}}}\times \sum _{k=0}^{n-r}\left({\frac {(-2)^{k}}{k!}}\times {2n-2r-2k \choose n-r-k}\right)$.
| Dénombrement des dérangements | Rencontre du troisième type |