Formule d'inversion de Pascal/Application au dénombrement des surjections
Une surjection d’un ensemble E dans un ensemble F est une application de E dans F où chaque élément de F admet au moins un antécédent.
Nous noterons Sp,n le nombre de surjections d’un ensemble de p éléments dans un ensemble de n éléments.
Nous allons trouver une formule exprimant Sp,n grâce à la formule d’inversion de Pascal.
Pour cela, nous remarquerons que le nombre des applications d’un ensemble de p éléments dans un ensemble de n éléments peut s’écrire comme la somme :
- du nombre d'applications où aucun élément de l’ensemble d’arrivée n'a d'antécédents ;
- du nombre d'applications où 1 seul élément de l’ensemble d’arrivée a des antécédents ;
- du nombre d'applications où 2 éléments de l’ensemble d’arrivée ont des antécédents ;
- …
- du nombre d'applications où les n éléments de l’ensemble d’arrivée ont des antécédents.
Pour calculer le nombre d’applications où exactement k éléments ont des antécédents, il suffit de dénombrer les choix des k éléments, soit , et de multiplier ensuite par le nombre de surjections vers les k éléments choisis, soit Sp,k.
Il y a donc applications où exactement k éléments de l’ensemble d’arrivée ont au moins un antécédent. Comme le nombre total d’applications d’un ensemble à p éléments vers un ensemble à n éléments est np, on peut écrire :
- ,
et c’est ici que nous pouvons utiliser la formule d’inversion de Pascal pour en déduire Sp,n.
Il suffit, pour fixé, de poser un = np et vn = Sp,n dans :
pour obtenir :
- .
On peut donc énoncer :
Le nombre Sp,n de surjections d’un ensemble de p éléments vers un ensemble de n éléments est donné par :
- .
Voir aussi : Formule du crible/Dénombrement des surjections et Combinatoire/Exercices/Combinaisons#Exercice 4-7.