Formule d'inversion de Pascal/Application au dénombrement des surjections

Début de la boite de navigation du chapitre


Nous noterons Sp,n le nombre de surjections d’un ensemble de p éléments dans un ensemble de n éléments.

Application au dénombrement des surjections
Icône de la faculté
Chapitre no 4
Leçon : Formule d'inversion de Pascal
Chap. préc. :Démonstration par récurrence
Chap. suiv. :Application au dénombrement des dérangements

Exercices :

Dénombrement des surjections
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Formule d'inversion de Pascal : Application au dénombrement des surjections
Formule d'inversion de Pascal/Application au dénombrement des surjections
 », n'a pu être restituée correctement ci-dessus.

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 :

Début d’un théorème
Fin du théorème


Voir aussi : Formule du crible/Dénombrement des surjections et Combinatoire/Exercices/Combinaisons#Exercice 4-7.