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

Nous noterons N_n 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 $(\binom{n}{k})$ possibilités. Puis effectivement déranger ces k éléments, soit N_k possibilités. Il y a donc $(\binom{n}{k})$ × N_k façons de déranger k éléments dans un ensemble de n éléments.

Nous pouvons donc écrire :

$n! = \sum_{k = 0}^{n} (\binom{n}{k}) N_{k}$

en posant u_n = n! et v_n = N_n dans la formule d’inversion de Pascal :

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

nous obtenons :

$\forall n \in ℕ n! = \sum_{k = 0}^{n} (\binom{n}{k}) N_{k} \Leftrightarrow N_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) k!$

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

$N_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) k!$

En remarquant que :

$(\binom{n}{k}) \times k! = \frac{n!}{(n - k)!}$

on peut écrire :

$N_{n} = n! \sum_{k = 0}^{n} \frac{(- 1)^{n - k}}{(n - k)!}$

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

$N_{n} = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$

Nous retiendrons :

Modèle:Théorème

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

Modèle:Bas de page

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

Menu de navigation

Rechercher