Leçons de niveau 15

Formule du crible/Dénombrement des dérangements

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


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 | modifier le wikicode]

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 :

Permutations4.gif

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

Ensemblepermut.png

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 | modifier le wikicode]

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 | modifier le wikicode]