Thèmes: Espaces probabilisés finis
- Nombre de surjections. $p$ personnes monte au RDC d'un immeuble de $n$ étages (sans compter le RDC).
Elles descendent toutes à un étage.
Quelle est la probabilité qu'à chaque étage au moins une personne soit descendue?
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?
Solution. 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 [\![ 1;n ]\!]$, 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$.
Pour terminer, 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 $$
- Nombre de dérangements. $n$ couples vont au bal.
Chaque femme choisit à l'aveugle un danseur parmi les $n$ hommes.
Quelle est la probabilité qu'aucune femme ne danse avec son propre mari?
Pour $k\in\mathbb{N}^*$, quelle est la probabilité qu'il y exactement $k$ femmes qui dansent avec leur propre mari?
Solution. 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 [\![ 1;n ]\!]$, 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$.
Pour terminer, 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 ! } $$
- 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 $[\![ 1;n ]\!]$.
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) $$
pù $\mathcal{P}_n$ désigne l'ensemble des nombres premiers qui divisent $n$
Solution. L'univers est $\Omega=[\![ 1;n ]\!]$. 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 [\![ 1;r ]\!]$, 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 $[\![ 1;n ]\!]$ 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 $[\![ 1;n ]\!]$ 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{ \frac{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) $$