- Formule du crible
-
Principe d'inclusion-exclusion
En combinatoire, le principe d’inclusion-exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d'une réunion finie d'ensembles finis en fonction du nombre d'éléments de ces ensembles et de leurs intersections. Il se traduit directement en termes de probabilités.
Il est attribué au mathématicien Abraham de Moivre, et connu également (lui ou sa version probabiliste) sous le nom de formule du crible de Poincaré, formule de Poincaré, ou formule du crible.
Sommaire
Le cas deux ensembles
Exemple
Parmi 20 étudiants, 10 étudient les mathématiques, 11 étudient la physique, et 4 étudient les deux. Combien y a-t-il d’étudiants qui n’étudient ni les mathématiques ni la physique ?
Pour visualiser nous pouvons construire un diagramme de Venn.
Nous entourons les éléments qui vérifient la même propriété. E représente le groupe entier d’étudiants, M représente ceux qui ont la propriété d'« étudier les mathématiques », P représente ceux qui possède la propriété : d'« étudier la physique ».
Nous plaçons dans chaque partie le nombre d’étudiants. Étant donné que quatre personnes étudient à la fois les mathématiques et la physique, nous reportons un 4 dans l’intersection des deux cercles. Nous devons donc avoir 10-4=6 personnes qui étudient les mathématiques mais pas la physique et 11-4=7 personnes qui étudient la physique mais pas les mathématiques. Il reste donc 20-(6+4+7)=3 personnes qui n’étudient ni les mathématiques ni la physique.
Ce résultat se retrouve facilement en utilisant le principe d’inclusion-exclusion qui donne le nombre d’étudiants ne possédant pas ces deux propriétés 20-10-11+4=3.
Formule pour n = 2
Soient A et B deux ensembles finis, la formule s'écrit
où |A| et |B| représentent les cardinaux respectifs de A et B.
En d’autres termes, nous pouvons compter les éléments de la réunion de deux ensembles A et B en additionnant les cardinaux de ces deux ensembles et en soustrayant le cardinal de leur intersection.
Cas général
Soient A1, ..., An n ensembles finis. Nous avons
où |A| désigne le cardinal d'un ensemble fini A.
Cette formule peut aussi s'écrire de façon plus condensée
- .
Elle peut se démontrer par récurrence sur n, ou en utilisant les fonctions indicatrices.
Soit E un ensemble fini, contenant les ensembles Ai. On déduit par passage au complémentaire le cardinal de l'ensemble des éléments de E qui n'appartiennent à aucun des Ai :
- .
Le principe d’inclusion-exclusion peut se déduire d'une formule d'inversion de Möbius.
Version probabiliste
Soient un espace probabilisé et éléments de la tribu Nous avons
- .
Cette formule peut se démontrer par récurrence sur n, ou en utilisant des fonctions indicatrices, de la même manière que la formule précédente.
Applications
Le terme d'ordre k de la somme décroit (en valeur absolue) en fonction de k. Les sommes partielles des premiers termes de la formule fournissent donc alternativement un majorant et un minorant de la somme complète, et peuvent être utilisées comme approximations de celle-ci.
En combinatoire, la formule du crible permet de déterminer le nombre de dérangements d'un ensemble fini. Un dérangement d'un ensemble A est une bijection de A sur lui-même sans point fixe. Grâce au principe d'inclusion-exclusion de Moivre, nous pouvons prouver que si le cardinal de A est égal à n, alors le nombre de dérangements de A est le nombre entier le plus proche de (où e désigne la base des logarithmes népériens).
Il s'ensuit que si toutes les bijections ont la même probabilité d'être choisies, alors la probabilité pour qu'une bijection prise au hasard soit un dérangement tend rapidement vers 1/e lorsque n tend vers l'infini.
- Portail des mathématiques
Catégorie : Analyse combinatoire
Wikimedia Foundation. 2010.