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

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 dérangements
Icône de la faculté
Chapitre no 5
Leçon : Formule d'inversion de Pascal
Chap. préc. :Application au dénombrement des surjections
Chap. suiv. :Démonstration polynomiale

Exercices :

Dénombrement des dérangements
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 dérangements
Formule d'inversion de Pascal/Application au dénombrement des dérangements
 », n'a pu être restituée correctement ci-dessus.


Nous noterons Nn le nombre de permutations d’un ensemble à n éléments ne laissant aucun point fixe, appelées aussi dérangements.

Le nombre total de permutations d’un ensemble à n élément étant n!, nous procéderons comme dans le chapitre précédent en décomposant celui-ci en la somme des nombres des applications dérangeant successivement k éléments pour k allant de 0 à n.

Pour déranger k éléments dans un ensemble à n éléments, il faut choisir les k éléments devant être dérangés, soit possibilités. Puis effectivement déranger ces k éléments, soit Nk possibilités. Il y a donc × Nk façons de déranger k éléments dans un ensemble de n éléments.

Nous pouvons donc écrire :

en posant un = n! et vn = Nn dans la formule d’inversion de Pascal :

nous obtenons :

Le nombre de dérangements d’un ensemble à n éléments est donc :

En remarquant que :

on peut écrire :

Et en faisant le changement d’indice k ↦ n - k, on obtient :


Nous retiendrons :

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


Voir aussi : Formule du crible/Dénombrement des dérangements.