Nombre d'applications : énoncé (MPSI)
Nombre d'applications
Si $E$ et $F$ sont finis, l'ensemble $F^E$ des applications de $E$ dans $F$ est fini et $$\operatorname{Card}(F^E)=(\operatorname{Card}F)^{\operatorname{Card}E}.$$
Démonstration : Nombre d'applications
Preuve
Notons $n=\operatorname{Card}E$, $p=\operatorname{Card}F$, et numérotons $E=\{x_1,\dots,x_n\}$. L'application $$\Phi:F^E\to F^n,\quad f\mapsto\big(f(x_1),\dots,f(x_n)\big)$$ est bijective : une application est entièrement déterminée par ses valeurs, et toute $n$-liste $(y_1,\dots,y_n)$ est l'image de l'unique $f$ telle que $f(x_i)=y_i$. Donc $\operatorname{Card}(F^E)=\operatorname{Card}(F^n)=p^n$.
Si $E=\varnothing$, il existe une seule application (l'application vide), et $p^0=1$ : la formule reste vraie.
Ordre des exposants
Le cardinal de l'ensemble d'arrivée est à la base, celui de départ est à l'exposant. Pour chaque élément de départ, on choisit une image parmi les éléments d'arrivée.
Exemple : il y a $3^5=243$ applications d'un ensemble à $5$ éléments dans un ensemble à $3$ éléments, et $5^3=125$ dans l'autre sens.
S’entraîner
- Applications et injections entre deux petits ensembles
- Répartition en binômes
- Injective implique bijective : usage et limites
- Surjections sur un ensemble à trois éléments
- Applications croissantes