Leçons de niveau 15

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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
Icon falscher Titel.svg
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é 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é 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.