Aller au contenu

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

Leçons de niveau 15
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
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 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 :

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.