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

Nous noterons S_p,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 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 ℕ$ fixé, de poser u_n = n^p et v_n = S_p,n dans :

(\forall n \in ℕ u_{n} = \sum_{k = 0}^{n} (\binom{n}{k}) v_{k}) \Leftrightarrow (\forall n \in ℕ v_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) u_{k})

pour obtenir :

(\forall n \in ℕ n^{p} = \sum_{k = 0}^{n} (\binom{n}{k}) S_{p, k}) \Leftrightarrow (\forall n \in ℕ S_{p, n} = \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) k^{p})

.

On peut donc énoncer :

Modèle:Théorème

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

Modèle:Bas de page

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

Menu de navigation

Rechercher