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

Début de la boite de navigation du chapitre

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

fin de la boite de navigation du chapitre

Définition

Nous appellerons dérangement, une permutation ne laissant aucun point fixe.

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 $\scriptstyle {n \choose k}$ possibilités. Puis effectivement déranger ces k éléments, soit N_k possibilités. Il y a donc $\scriptstyle {n \choose 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}{n \choose k}N_{k}$

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

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

nous obtenons :

$\forall n\in \mathbb {N} \quad n!=\sum _{k=0}^{n}{n \choose k}N_{k}\Leftrightarrow N_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k!$

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

$N_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k!$

En remarquant que :

${n \choose 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 :

Début d’un théorème

Théorème

Le nombre de permutations d’un ensemble à n éléments ne laissant aucun point fixe, appelées aussi dérangements, est donné par :

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

Fin du théorème

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