Correction de l'exercice

L'expérience consiste à répartir $10$ souris dans $10$ boîtes. Une répartition est une application de l'ensemble des $10$ souris vers l'ensemble des $10$ boîtes. L'univers $\Omega$ a pour cardinal : $\text{Card}(\Omega) = 10^{10}$.

1. Aucune boîte vide

   Cela signifie que chaque boîte contient exactement une souris. Il s'agit des bijections de l'ensemble des souris vers l'ensemble des boîtes.

   \[ \text{Cas favorables} = 10! \] \[ p_1 = \frac{10!}{10^{10}} \]



2. Exactement une boîte vide

   Avoir exactement une boîte vide implique qu'une boîte contient $2$ souris, et les $8$ autres boîtes occupées contiennent $1$ souris chacune. On dénombre les cas favorables étape par étape :

   • Choix de la boîte vide : $C_{10}^1 = 10$ possibilités.
   • Choix de la boîte contenant $2$ souris : $C_9^1 = 9$ possibilités.
   • Choix des $2$ souris pour cette boîte : $C_{10}^2 = 45$ possibilités.
   • Répartition des $8$ souris restantes dans les $8$ boîtes restantes : $8!$ bijections possibles.
   \[ \text{Cas favorables} = 10 \times 9 \times 45 \times 8! = 45 \times 10! \] \[ p_2 = \frac{45 \times 10!}{10^{10}} \]



3. Exactement 5 boîtes vides

   Cela signifie qu'exactement $5$ boîtes sont occupées par les $10$ souris (aucune des 5 n'est vide). Le nombre de répartitions correspond au choix de ces $5$ boîtes, multiplié par le nombre d'applications surjectives des $10$ souris vers ces $5$ boîtes.

   • Choix des $5$ boîtes occupées : $C_{10}^5$ possibilités.
   • Nombre de surjections : $S(10,5) = (-1)^5 \sum_{k=1}^5 (-1)^k C_5^k k^{10}$.
   \[ \text{Cas favorables} = C_{10}^5 \times S(10,5) \] \[ p_3 = \frac{C_{10}^5 \times S(10,5)}{10^{10}} \]

Tirage d'une boîte au hasard

1. La probabilité qu'une boîte spécifique (fixée à l'avance) soit vide correspond à la probabilité que les $10$ souris aient choisi de se cacher parmi les $9$ autres boîtes :

   \[ P(\text{Boîte fixée vide}) = \frac{9^{10}}{10^{10}} = \left(\frac{9}{10}\right)^{10} \]

   Puisque la personne choisit une boîte au hasard de manière totalement indépendante de la répartition des souris, la probabilité que la boîte tirée soit vide est identique (cela se démontre rigoureusement par la formule des probabilités totales).

   \[ P(\text{Boîte tirée vide}) = \left(\frac{9}{10}\right)^{10} \]

Pour aller plus loin : Surjections et relation d'équivalence

Il existe une démonstration particulièrement élégante reliant le nombre de surjections $S(n,p)$ aux partitions d'un ensemble (les nombres de Stirling de seconde espèce), en utilisant les relations d'équivalence.

1. La relation d'équivalence associée à une surjection

   Soit $E$ un ensemble à $n$ éléments (nos $10$ souris) et $F$ un ensemble à $p$ éléments (nos $5$ boîtes).

   Pour toute application surjective $f : E \longrightarrow F$, on définit sur $E$ la relation $\mathcal{R}_f$ par :

   \[ \forall (x,y) \in E^2, \quad x \mathcal{R}_f y \iff f(x) = f(y) \]

   Cette relation (qui signifie "être dans la même boîte") est trivialement réflexive, symétrique et transitive. C'est une relation d'équivalence.




2. L'ensemble quotient et la partition

   Les classes d'équivalence de cette relation regroupent les éléments de $E$ ayant la même image par $f$.

   • Puisque $f$ est surjective, chaque élément de $F$ a au moins un antécédent. Il y a donc exactement $p$ classes d'équivalence non vides.
   • L'ensemble quotient $E/\mathcal{R}_f$ (l'ensemble de ces classes) constitue une partition de l'ensemble $E$ en exactement $p$ sous-ensembles.

   Par définition, le nombre de façons de partitionner un ensemble de $n$ éléments en $p$ sous-ensembles non vides est le nombre de Stirling de seconde espèce, noté $\left\{\begin{matrix}n\\p\end{matrix}\right\}$.




3. Le dénombrement final (Théorème de bijection)

   Fixons une partition donnée de $E$ en $p$ classes. Combien de surjections $f$ génèrent cette partition exacte ?

   Pour construire une telle surjection, il suffit d'associer chacune des $p$ classes d'équivalence à un élément distinct de l'ensemble d'arrivée $F$. Cela revient à créer une bijection entre l'ensemble quotient (de cardinal $p$) et $F$ (de cardinal $p$).

   Il y a exactement $p!$ bijections possibles.

   En vertu du principe multiplicatif, on obtient la formule fondamentale :

   \[ S(n,p) = p! \times \left\{\begin{matrix}n\\p\end{matrix}\right\} \]

Calcul manuel du nombre de Stirling:

Le nombre de façons de partitionner un ensemble de $10$ éléments en $5$ sous-ensembles non vides est le nombre de Stirling de seconde espèce, noté $\left\{\begin{matrix}10\\5\end{matrix}\right\}$. On peut le retrouver formellement en dénombrant toutes les décompositions possibles de l'entier $10$ en une somme de $5$ entiers strictement positifs.

1. Les 7 structures de partition de l'entier 10

   Il n'existe que $7$ façons de décomposer $10$ en somme de $5$ entiers (l'ordre des termes n'ayant pas d'importance) :

   • Structure 1 : $6 + 1 + 1 + 1 + 1$
   • Structure 2 : $5 + 2 + 1 + 1 + 1$
   • Structure 3 : $4 + 3 + 1 + 1 + 1$
   • Structure 4 : $4 + 2 + 2 + 1 + 1$
   • Structure 5 : $3 + 3 + 2 + 1 + 1$
   • Structure 6 : $3 + 2 + 2 + 2 + 1$
   • Structure 7 : $2 + 2 + 2 + 2 + 2$



2. Dénombrement des répartitions pour chaque structure

   Pour chaque décomposition, on calcule le nombre de répartitions possibles (choix des souris pour chaque groupe) à l'aide des coefficients multinomiaux.
   Attention : Il est impératif de diviser par la factorielle du nombre de groupes de même taille pour ne pas compter plusieurs fois la permutation de groupes devenus indiscernables.

   • $6+1+1+1+1$ (quatre groupes de $1$) : $\frac{10!}{6! \times (1!)^4} \times \frac{1}{4!} = 210$
   • $5+2+1+1+1$ (trois groupes de $1$) : $\frac{10!}{5! \times 2! \times (1!)^3} \times \frac{1}{3!} = 2\,520$
   • $4+3+1+1+1$ (trois groupes de $1$) : $\frac{10!}{4! \times 3! \times (1!)^3} \times \frac{1}{3!} = 4\,200$
   • $4+2+2+1+1$ (deux groupes de $2$, deux de $1$) : $\frac{10!}{4! \times (2!)^2 \times (1!)^2} \times \frac{1}{2! \times 2!} = 9\,450$
   • $3+3+2+1+1$ (deux groupes de $3$, deux de $1$) : $\frac{10!}{(3!)^2 \times 2! \times (1!)^2} \times \frac{1}{2! \times 2!} = 12\,600$
   • $3+2+2+2+1$ (trois groupes de $2$) : $\frac{10!}{3! \times (2!)^3 \times 1!} \times \frac{1}{3!} = 12\,600$
   • $2+2+2+2+2$ (cinq groupes de $2$) : $\frac{10!}{(2!)^5} \times \frac{1}{5!} = 945$



3. Bilan et lien avec les surjections

   En sommant ces résultats, on obtient exactement le nombre de Stirling de seconde espèce :

   \[ \left\{\begin{matrix}10\\5\end{matrix}\right\} = 210 + 2\,520 + 4\,200 + 9\,450 + 12\,600 + 12\,600 + 945 = 42\,525 \]

   Enfin, pour retrouver le nombre d'applications surjectives $S(10,5)$, il suffit de distribuer ces $5$ groupes non vides dans les $5$ boîtes distinctes (soit $5!$ bijections possibles) :

   \[ S(10,5) = 5! \times \left\{\begin{matrix}10\\5\end{matrix}\right\} = 120 \times 42\,525 = 5\,103\,000 \]