Exercice 34

L'univers est l'ensemble $E^{E}$ des applications de $E$ dans $E$, de cardinal $n^{n}$ (proposition 3), muni de la probabilité uniforme.

1. Supposons $f \circ f = f$ et soit $y \in f(E)$, de la forme $y = f(x)$. Alors $f(y) = f(f(x)) = f(x) = y$. Réciproquement, si $f(y) = y$ pour tout $y \in f(E)$, alors, pour tout $x \in E$, l'élément $f(x)$ appartient à $f(E)$, donc $f(f(x)) = f(x)$. $$\boxed{f \circ f = f \iff f(y) = y \ \text{ pour tout } y \in f(E)}$$ C'est la question 2 de l'exercice 18 de la feuille du chapitre 2, avec sa réciproque.

2. On classe les applications $f$ telles que $f \circ f = f$ selon leur image $F = f(E)$, qui est une partie non vide de $E$, puisque $E$ ne l'est pas. Soit $F$ une partie à $k \geqslant 1$ éléments. D'après la question 1, une application $f$ telle que $f \circ f = f$ et $f(E) = F$ vaut l'identité sur $F$, et envoie chacun des $n - k$ éléments de $E \setminus F$ dans $F$. Réciproquement, une telle application a pour image $F$ (elle contient $F$, puisque $f$ fixe les points de $F$, et elle est contenue dans $F$), et vérifie donc $f \circ f = f$ par la question 1. Il y en a autant que d'applications de $E \setminus F$ dans $F$, soit $k^{n-k}$ (proposition 3). Il y a $\binom{n}{k}$ parties $F$ à $k$ éléments (théorème 2), et la proposition 2 (i) donne $$\boxed{\big|\{f \in E^{E} \mid f \circ f = f\}\big| = \sum_{k=1}^{n} \dbinom{n}{k}k^{n-k}, \qquad p_{n} = \frac{1}{n^{n}}\sum_{k=1}^{n} \dbinom{n}{k}k^{n-k}}$$ Pour $n = 1$, …, $6$, on trouve $1$, $3$, $10$, $41$, $196$, $1\,057$ applications, nombres confirmés par une énumération des $n^{n}$ applications ✓. Pour $n = 3$, ce sont l'identité, les $3$ applications constantes, et les $6$ applications d'image à deux éléments.

3. Soit $n \geqslant 2$. Comme $\binom{n}{k} = \frac{n(n - 1)\cdots(n - k + 1)}{k!} \leqslant \frac{n^{k}}{k!}$, le terme d'indice $k$ de $p_{n}$ vérifie $$0 \leqslant u_{k} = \frac{1}{n^{n}}\dbinom{n}{k}k^{n-k} \leqslant \frac{n^{k}k^{n-k}}{k!\,n^{n}} = \frac{1}{k!}\Big(\frac{k}{n}\Big)^{n-k}.$$

• Si $k \leqslant \frac{n}{2}$, alors $\frac{k}{n} \leqslant \frac{1}{2}$ et $n - k \geqslant \frac{n}{2}$, donc $u_{k} \leqslant \frac{1}{k!}\,2^{-n/2}$. En sommant, et comme $\sum_{k \geqslant 1} \frac{1}{k!} = \mathrm{e} - 1$ (chapitre 20, théorème 2), la somme de ces termes est majorée par $(\mathrm{e} - 1)\,2^{-n/2}$.

• Si $k > \frac{n}{2}$, alors $k \geqslant m$, avec $m = \lfloor n/2 \rfloor + 1$, et $\big(\frac{k}{n}\big)^{n-k} \leqslant 1$, donc $u_{k} \leqslant \frac{1}{m!}$. Il y a au plus $n \leqslant 2m$ tels termes, de somme majorée par $\frac{2m}{m!} = \frac{2}{(m - 1)!}$.

$$\boxed{0 \leqslant p_{n} \leqslant (\mathrm{e} - 1)\,2^{-n/2} + \frac{2}{\lfloor n/2 \rfloor!} \xrightarrow[n \to +\infty]{} 0}$$ Numériquement, $p_{5} \approx 0{,}063$, $p_{10} \approx 2{,}2 \times 10^{-4}$ et $p_{20} \approx 2{,}6 \times 10^{-10}$ : la décroissance est bien plus rapide que ne le dit le majorant, qui ne sert qu'à établir la limite.

Piège. Majorer chaque terme par une quantité qui tend vers $0$ ne suffit pas, puisque le nombre de termes augmente avec $n$ : l'erreur la plus répandue est d'oublier ce nombre. La séparation en deux paquets répond à deux difficultés distinctes. Pour $k$ petit, c'est le facteur $\big(\frac{k}{n}\big)^{n-k}$ qui est minuscule, et la série exponentielle contrôle la somme des $\frac{1}{k!}$ ; pour $k$ grand, ce facteur peut être proche de $1$, mais $\frac{1}{k!}$ écrase le nombre $n$ de termes.