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

Début de la boite de navigation du chapitre

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

fin de la boite de navigation du chapitre

Rappel

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 allons trouver une formule exprimant S_p,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 ${\binom {n}{k}}$, et de multiplier ensuite par le nombre de surjections vers les k éléments choisis, soit S_p,k.

Il y a donc ${\binom {n}{k}}S_{p,k}$ 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 n^p, on peut écrire :

$n^{p}=\sum _{k=0}^{n}{\binom {n}{k}}S_{p,k}$,

et c’est ici que nous pouvons utiliser la formule d’inversion de Pascal pour en déduire S_p,n.

Il suffit, pour $p\in \mathbb {N}$ fixé, de poser u_n = n^p et v_n = S_p,n dans :

$\left(\forall n\in \mathbb {N} \quad u_{n}=\sum _{k=0}^{n}{\binom {n}{k}}v_{k}\right)\Leftrightarrow \left(\forall n\in \mathbb {N} \quad v_{n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}u_{k}\right)$

pour obtenir :

$\left(\forall n\in \mathbb {N} \quad n^{p}=\sum _{k=0}^{n}{\binom {n}{k}}S_{p,k}\right)\Leftrightarrow \left(\forall n\in \mathbb {N} \quad S_{p,n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{p}\right)$.

On peut donc énoncer :

Début d’un théorème

Théorème

Le nombre S_p,n de surjections d’un ensemble de p éléments vers un ensemble de n éléments est donné par :

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

Fin du théorème

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