Applications de la formule du crible de Poincaré

Menu

1. Nombre de surjections.

$p$ personnes monte au RDC d'un immeuble de $n$ étages (sans compter le RDC).
Elles descendent toutes à un étage.

1. Quelle est la probabilité qu'à chaque étage au moins une personne soit descendue?
2. Pour $k\in\mathbb{N}^*$, quelle est la probabilité qu'il y ait $k$ étages auxquels personne ne descend, et $n-k$ étages auxquels au moins une personne est descendue?

1. On choisit comme univers $\Omega$ l'ensemble de toutes les applications de l'ensemble des $p$ personnes dans l'ensemble des $n$ étages, et on le munit de la probabilité uniforme.
   On sait que $ \hbox{ Card } ( \Omega ) = n^p $.
   On note E = " à chaque étage au moins une personne est descendue ".
   Pour $k\in \lc 1,n \rc$, on note aussi $A_k$ = " au moins une personne est descendue à l'étage numéro $k$ ".
   Il est clair que : $$ E = \bigcap_{k=1}^n A_k $$ et donc : $$ \overline{E} = \bigcup_{ k=1 }^n \overline{ A_k } $$ Les $A_k$ ne sont clairement pas incompatibles (toutes les personnes ne descendents pas nécessairement au même étage!), on a donc recours à la formule du crible : $$ \mathbb{P} ( \overline{E} ) = \sum_{k=1}^n (-1)^{k-1} \left( \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n} \mathbb{P} ( \overline{ A_{i_1} } \cap \overline{ A_{i_2} } \cap \dots \cap \overline{ A_{i_k} } ) \right) $$ Pour $i_1$, $i_2$, $\dots$, $i_k$ fixés tels que $1\leq i_1 < i_2 < \dots < i_k \leq n$, $\hbox{Card} ( \overline{ A_{i_1} } \cap \overline{ A_{i_2} } \cap \dots \cap \overline{ A_{i_k} } )$ est égale au nombre d'applications de l'ensemble des $n$ personnes dans l'ensemble des $p$ étages autres que les étages $i_1$, $i_2$, $\dots$, $i_k$. Ce nombre est donc égal à $(n-k)^p$.
   Puisqu'il ne dépend pas des valeurs $i_1$, $i_2$, $\dots$, $i_k$ (mais seulement de $k$) et comme le nombre de termes de la somme $\displaystyle \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n}$ est égal à $\displaystyle \binom{n}{k}$ (on choisit une combinaison de $k$ valeurs distinctes et il y a ensuite une seule façon de les ordonner dans l'ordre strictement croissant), on a : $$ \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n} \mathbb{P} ( \overline{ A_{i_1} } \cap \overline{ A_{i_2} } \cap \dots \cap \overline{ A_{i_k} } ) = \binom{n}{k} \left(\frac{n-k}{n}\right) ^p $$ On en déduit que : $$ \mathbb{P} ( \overline{E} ) = \sum_{k=1}^n (-1)^{k-1} \binom{n}{k} \left(\frac{n-k}{n}\right)^p $$ et donc : $$\mathbb{P} ( E ) = 1 -  \mathbb{P} ( \overline{E} ) = \sum_{k=0}^n (-1)^{k} \binom{n}{k} \left(\frac{n-k}{n}\right)^p $$ Le changement de variable $k'=n-k$ et la symétrie des coefficients binômiaux donnent enfin que : $$\mathbb{P} ( E ) = 1 -  \mathbb{P} ( \overline{E} ) = (-1)^n\sum_{k=0}^n (-1)^{k} \binom{n}{k} \left(\frac{k}{n}\right)^p $$ Si on note $S^p_n$ le nombre de surjections d'un ensemble à $p$ éléments vers un ensemble à $n$ éléments, on a $\displaystyle \mathbb{P} ( E ) = \frac{ S^p_n }{ n^p }$.
   On en déduit que : $$ S^p_n = (-1)^n\sum_{k=0}^n (-1)^{k} \binom{n}{k} k^p $$ pour tout entiers naturels non nuls $n$ et $p$.
2. Notons $F_k$ = " il y a $k$ étages auxquels personne n'est descendu, et $n-k$ autres auxquels au moins une personne est descendues ".
   $\hbox{ Card } ( F_k ) $ est égal au nombre de choix des $k$ étages, multiplié par le nombre de façons que les $p$ personnes descendent surjectivement aux $n-k$ autres étages, ie : $$ \hbox{Card} ( F_k ) =\binom{n}{k} \times  S^{p}_{n-k} $$ donc : $$\hbox{Card} ( F_k ) =\binom{n}{k}(-1)^{n-k}\sum_{i=0}^{n-k} (-1)^i \binom{n-k}{i} i^p $$ et : $$ \mathbb{P} ( F_k ) = \binom{ n }{ k } (-1)^{n-k}\sum_{i=0}^{n-k} (-1)^i \binom{n-k}{i} \left(\frac{i}{n}\right)^p $$

MASQUER

2. Nombre de dérangements.

$n$ couples vont au bal.
Chaque femme choisit à l'aveugle un danseur parmi les $n$ hommes.

1. Quelle est la probabilité qu'aucune femme ne danse avec son propre mari?
2. Pour $k\in\mathbb{N}^*$, quelle est la probabilité qu'il y exactement $k$ femmes qui dansent avec leur propre mari?

1. On choisit comme univers $\Omega$ l'ensemble de toutes permutations des $n$ hommes, et on le munit de la probabilité uniforme.
   On sait que $ \hbox{ Card } ( \Omega ) = n! $.
   On note E = " aucune femme ne danse avec son propre mari ".
   Pour $k\in \lc 1,n \rc$, on note aussi $A_k$ = " l'homme numéro $k$ dans avec sa propre femme ".
   Il est clair que : $$ E = \bigcap_{k=1}^n \overline{A_k} $$ et donc : $$ \overline{E} = \bigcup_{ k=1 }^n A_k $$ Les $A_k$ ne sont clairement pas incompatibles (il est possible que plusieurs hommes dansent avec leur propre femme), on a donc recours à la formule du crible : $$ \mathbb{P} ( \overline{E} ) =\sum_{k=1}^n (-1)^{k-1} \left( \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n} \mathbb{P} ( A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} ) \right) $$ Pour $i_1$, $i_2$, $\dots$, $i_k$ fixés tels que $1\leq i_1 < i_2 < \dots < i_k \leq n$, $\hbox{Card} ( A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} )$ est égale au nombre de permutations des $n$ hommes qui laissent fixe les hommes numéro $i_1$, $i_2$, $\dots$, $i_k$ (et peut-être d'autres...).
   Ceci reveint à permuter les $n-k$ autres hommes, ce nombre est donc égal à $(n-k)!$ .
   Puisqu'il ne dépend pas des valeurs $i_1$, $i_2$, $\dots$, $i_k$ (mais seulement de $k$) et comme le nombre de termes de la somme $\displaystyle \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n}$ est égal à $\displaystyle \binom{n}{k}$ (on choisit une combinaison de $k$ valeurs distinctes et il y a ensuite une seule façon de les ordonner dans l'ordre strictement croissant), on a: $$ \sum_{1\leq i_1 < i_2 < \dots < i_k \leq n} \mathbb{P} ( A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} ) = \binom{n}{k} \frac{ (n-k) ! }{ n ! }$$ On en déduit que : $$ \mathbb{P} ( \overline{E} ) = \sum_{k=1}^n (-1)^{k-1} \binom{n}{k} \frac{ ( n-k ) ! }{ n ! } = \sum_{k=1}^n \frac{ (-1)^{k-1} }{ k! }$$ et donc : $$\mathbb{P} ( E ) = 1 -  \mathbb{P} ( \overline{E} ) = \sum_{k=0}^n \frac{ (-1)^{k} }{ k ! }$$ Si on note $d_n$ le nombre de dérangements d'un ensemble à $n$ éléments, c'est-à-dire le nombre de permutations sans point fixe, on a $\displaystyle \mathbb{P} ( E ) = \frac{ d_n }{ n ! }$.
   On en déduit que : $$ d_n = n ! \sum_{k=0}^n \frac{ (-1)^{k} }{ k ! }$$ pour tout entiers naturel non nul $n$.
2. Notons $F_k$ = " il y a exactement $k$ femmes qui dansent avec leur propre mari ".
   $\hbox{ Card } ( F_k ) $ est égal au nombre de choix possibles des $k$ femmes, multiplié par le nombre de façons que les $n-k$ autres femmes ne dansent pas avec leur mari, ie : $$ \hbox{Card} ( F_k ) = \binom{n}{k} \times d_{n-k} $$ donc : $$\hbox{Card} ( F_k ) =\binom{n}{k} (n-k) ! \sum_{i=0}^{n-k} \frac{ (-1)^i }{ i ! }  $$ et : $$ \mathbb{P} ( F_k ) = \frac{ 1 }{ k ! } \sum_{i=0}^{n-k} \frac{ (-1)^i }{ i ! } $$

MASQUER

3. Calcul de la fonction arithmétique d'Euler.

$\varphi(n)$ désigne le nombre d'entiers naturels inférieurs ou égaux à $n$, premiers avec $n$.
Rappelons qu'un entier naturel $k$ est premier avec $n$ lorsque, pour $d\in\mathbb{N}^*$, $d | k$ et $d | n$ donne $d=1$.
On fixe $n\in \mathbb{N}^*$, et on choisit au hasard un élément de $\lc 1,n \rc$.
Déterminer de deux manières différentes la probabilité qu'il soit premier avec $n$ (on pourra utiliser la décomposition de $n$ en facteurs premiers).
En déduire la formule : $$ \frac{\varphi(n)}{n} = \prod_{ p\in\mathcal{P}_n } \left( 1 - \frac{1}{p} \right) $$ où $\mathcal{P}_n$ désigne l'ensemble des nombres premiers qui divisent $n$.

L'univers est $\Omega=\lc 1,n \rc$.
On note $E$ l'évènement "le nombre choisit est premier avec $n$ ".
Il est clair que : $$ \mathbb{P} ( E ) = \frac{\varphi(n)}{n} $$ Déterminons ensuite cette probabilité en utilisant la formule du crible de Poincaré.
On note aussi $n=p_1^{ \alpha_1} p_2^{\alpha_2 } \dots p_r ^{\alpha_r}$ la décomposition de $n$ en facteurs premiers, et, pour tout $k\in \lc1,r\rc$, on note $A_k$ l'évènement " le nombre choisit est divisible par $p_k$ ".
On remarque alors que $\displaystyle E = \bigcap_{k=1}^r \overline{A_k} $ et donc que $ \overline{E} = \bigcup_{k=1}^r A_k$.
On en déduit que : $$ \mathbb{P} \big( \overline{E} \big) = \sum_{k=1}^r (-1)^{k-1} \left( \sum_{ 1 \leq i_1 < i_2 < \dots < i_k \leq r } \mathbb{P} \big( A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \big) \right) $$ Pour $1\leq i_1 < \dots < i_k \leq r$, l'évènement $ A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}$ est l'ensemble des éléments de $\lc 1,n \rc$ qui sont divisibles par les nombres premiers $p_{i_1}$, $p_{i_2}$, $\dots$, $p_{i_k}$, ou de manière équivalente (d'après le lemme de Gauss), qui sont divisibles par le produit $p_{i_1} p_{i_2} \dots p_{i_k}$.
Mais si $d\in\mathbb{N}^*$ divise $n$, les éléments de $\lc 1,n \rc$ divisibles par $d$ sont de la forme $kd$, où $\displaystyle k \in \left[\!\!\left[1;\frac{n}{d} \right]\!\!\right]$.
Ils sont donc au nombre de $\displaystyle \frac{n}{d} $.
On en déduit que : $$ \mathbb{P} \big( A_{i_1} \cap \dots \cap A_{i_k} \big) = \frac{\;\; \dfrac{n}{ p_{i_1} p_{i_2} \dots p_{i_k} } \;\;}{ n } = \frac{1}{ p_{i_1} p_{i_2} \dots p_{i_k} } $$ On a donc : $$ \mathbb{P} \big( \overline{E} \big)= 1 -\frac{\varphi(n) }{ n } = \sum_{k=1}^r (-1)^{k-1} \sum_{1\leq i_1 < \dots < i_k \leq r } \frac{1}{ p_{i_1} p_{i_2} \dots p_{i_k} } $$ d'où : $$ \frac{ \varphi(n) }{ n } = 1+ \sum_{k=1}^n (-1)^k \sum_{1\leq i_1 < \dots < i_k \leq r } \frac{1}{ p_{i_1} \dots p_{i_k} } = \prod_{k=1}^r \left(1 - \frac{1}{ p_k } \right) $$ MASQUER