Formule du crible/Dénombrement des dérangements

Début de la boite de navigation du chapitre
Dénombrement des dérangements
Icône de la faculté
Chapitre no 5
Leçon : Formule du crible
Chap. préc. :Dénombrement des surjections
Chap. suiv. :Rencontre du second type

Exercices :

sur le dénombrement des dérangements
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Formule du crible : Dénombrement des dérangements
Formule du crible/Dénombrement des dérangements
 », n'a pu être restituée correctement ci-dessus.

Définition

modifier


Nous désignerons par Nn le nombre de dérangements d'un ensemble E à n éléments.

Sans nuire à la généralité, nous pouvons supposer que E = {1, 2, … , n}.

Nous savons qu’il y a n! permutations de E.

Dans cette étude, nous noterons Ai l’ensemble des permutations de E laissant fixe au moins le point i.

AiAj représente alors l’ensemble des permutations de E laissant au moins i et j fixes.

AiAj représente l’ensemble des permutations laissant au moins i ou j fixes.

L’ensemble des dérangements de E est alors :

 .

Exemple

modifier

Soit E = {1, 2, 3, 4} de cardinal 4. Il y a 4! = 24 permutations de cet ensemble.

Celle-ci peuvent être représentées par :

 

En répartissant les différentes permutations dans les ensembles A1, A2, A3, A4, nous obtenons :

 

Nous voyons alors qu’il y a 9 dérangements de E, à savoir h, j, l, n, q, r, s, w et x.

Cas général

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


Début d'une démonstration
Fin de la démonstration

Pour un calcul de probabilité, Nn sera divisé par le nombre de permutations de E, à savoir n! ; il restera :

 .

Nous remarquons que

 .

La convergence est très rapide puisque nous avons des factorielles en dénominateur. À tel point que pour un ensemble d'au moins six éléments, la probabilité de tomber sur un dérangement parmi ces permutations pourra être prise égale à e–1 avec une erreur inférieure au millième. (Avec un ensemble à 4 éléments, l'erreur est inférieure au centième.)

Probabilité qu'une permutation laisse r points fixes

modifier