Formule du crible/Rencontre du second type

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

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 :

Début d’un théorème

Théorème

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)$.

Fin du théorème