Formule du crible/Dénombrement des surjections

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Début d’un théorème

Théorème

Soient $p,q\in \mathbb {N}$. Le nombre $S_{p,q}$ de surjections d'un ensemble à $p$ éléments dans un ensemble à $q$ éléments est donné par :

$S_{p,q}=\sum _{k=0}^{q}(-1)^{q-k}{\binom {q}{k}}k^{p}$.

Fin du théorème

Début d'une démonstration

Démonstration

Supposons que $|X|=p$ et $|Y|=q$.

Pour tout $y\in Y$, soit $A_{y}$ l'ensemble des applications de $X$ dans $Y$ qui ne prennent jamais la valeur $y$. Une surjection de $X$ dans $Y$ est alors une application de $X$ dans $Y$ qui n'est dans aucun $A_{y}$. On a donc

$S_{p,q}=\left|Y^{X}\setminus \cup _{y\in Y}A_{y}\right|=q^{p}-\left|\cup _{y\in Y}A_{y}\right|$.

Or d'après la formule du crible,

$\left|\cup _{y\in Y}A_{y}\right|=\sum _{k=1}^{q}(-1)^{k-1}\sum _{Z\subset Y \atop |Z|=k}\left|A_{Z}\right|$,

où $A_{Z}:=\cap _{y\in Z}A_{y}$ est l'ensemble des applications de $X$ dans $Y$ pour lesquelles aucun élément de $Z$ n’a d'antécédent. Il y en a autant que d'applications de $X$ dans $Y\setminus Z$, c'est-à-dire :

$\left|A_{Z}\right|=\left(q-|Z|\right)^{p}$

et en reportant :

${\begin{aligned}\left|\cup _{y\in Y}A_{y}\right|&=\sum _{k=1}^{q}(-1)^{k-1}\sum _{Z\subset Y \atop |Z|=k}(q-k)^{p}\\&=\sum _{k=1}^{q}(-1)^{k-1}(q-k)^{p}\left|\{Z\subset Y\mid |Z|=k\}\right|\\&=\sum _{k=1}^{q}(-1)^{k-1}{\binom {q}{k}}(q-k)^{p}\end{aligned}}$

puis

${\begin{aligned}S_{p,q}&=q^{p}-\left|\cup _{y\in Y}A_{y}\right|\\&=q^{p}-\sum _{k=1}^{q}(-1)^{k-1}{\binom {q}{k}}(q-k)^{p}\\&=\sum _{k=0}^{q}(-1)^{k}{\binom {q}{k}}(q-k)^{p}\\&=\sum _{j=0}^{q}(-1)^{q-j}{\binom {q}{q-j}}j^{p}\\&=\sum _{j=0}^{q}(-1)^{q-j}{\binom {q}{j}}j^{p}.\end{aligned}}$

Fin de la démonstration

Remarques

• On trouvera une autre démonstration de ce théorème dans la leçon « Formule d'inversion de Pascal », et encore une autre dans l'exercice 4-7 de la leçon « Combinatoire ».
• Pour $q=0$, le théorème donne $S_{p,0}=0^{p}$. Effectivement, $S_{0,0}=1$ (l'unique application de $\varnothing$ dans $\varnothing$ est bien surjective), et $S_{p,0}=0$ si $p>0$ (il n'y a pas d'application d'un ensemble non vide dans $\varnothing$).
• Pour $q=p$, les surjections sont les bijections donc $S_{p,p}=p!$.
• Pour $q>p$, $S_{p,q}=0$.
• Les ${\frac {S_{p,q}}{q!}}$ sont appelés les nombres de Stirling de seconde espèce. C'est le nombre, pour un ensemble de cardinal $p$, de partitions en $q$ sous-ensembles ou, ce qui revient au même, de relations d'équivalence ayant $q$ classes.