Principe d'inclusion-exclusion

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple d'inclusion-exclusion à partir de trois ensembles.

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.

Le cas de deux ensembles[modifier | modifier le code]

Exemple[modifier | modifier le code]

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.

Inclusion exclusion.png

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[modifier | modifier le code]

Soient A et B deux ensembles finis, la formule s'écrit

|A\cup B|=|A|+|B|-|A\cap B|

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[modifier | modifier le code]

Soient A1, ..., An n ensembles finis. Nous avons

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{i=1}^n\left|A_i\right|
-\sum_{(i,j)\,/\,1\leq i<j\leq n}\left|A_i\cap A_j\right| + \sum_{(i,j,k)\,/\,1\leq i<j<k\leq n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ +(-1)^{n+1}|A_1\cap\ldots\cap A_n|

où |A| désigne le cardinal d'un ensemble fini A.

Cette formule peut aussi s'écrire de façon plus condensée

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right|\right).

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 :

\left|E\setminus\bigcup_{i=1}^n A_i\,\right|=|E|+\sum_{k=1}^n \left((-1)^{k} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right|\right).

Le principe d’inclusion-exclusion peut se déduire d'une formule d'inversion de Möbius.

Version probabiliste[modifier | modifier le code]

Soient un espace probabilisé \scriptstyle\ (\Omega,\mathcal{A},\mathbb{P})\ et \scriptstyle\ n\ éléments \scriptstyle\ A_1, A_2, \dots,A_n\ de la tribu \scriptstyle\ \mathcal{A}.\ Nous avons

\mathbb{P}\left(\,\bigcup_{i=1}^n A_i\,\right)=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \mathbb{P}\left(A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right)\right).

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. On peut aussi la formuler de la manière suivante :

\mathbb{P}\left(\,\bigcup_{i=1}^n A_i\,\right)=\sum_{S\subset[\![1,n]\!],\,S\neq\varnothing} (-1)^{-1+|S|}\   \mathbb{P}\left(\bigcap_{i\in S}\,A_{i}\right).

Applications[modifier | modifier le code]

Inégalités de Bonferroni[modifier | modifier le code]

Les sommes partielles des premiers termes de la formule fournissent alternativement un majorant et un minorant de la somme complète, et peuvent être utilisées comme approximations de celle-ci : ces majorations et minorations sont appelées les inégalités de Bonferroni, du nom de leur auteur, Carlo Emilio Bonferroni.

Dérangements et nombre de points fixes d'une permutation[modifier | modifier le code]

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 n!/e (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.

On peut pousser plus loin l'étude statistique des points fixes des permutations. Notons N(ω) le nombre de points fixes d'une permutation ω. On remarque que N(ω)=0 si et seulement si ω est un dérangement. En cela la proposition suivante précise le résultat concernant les dérangements (qui n'est autre que le calcul de \scriptstyle\ \mathbb{P}\left(\,N=0\right)\ ) :

Proposition — Pour tout entier k compris entre 0 et n,

\mathbb{P}\left(\,N=k\right)\ =\ \frac{1}{k!}\quad\sum_{\ell=0}^{n-k}\ \frac{(-1)^{\ell}}{\ell!}.

En particulier, la loi de N est très proche de la loi de Poisson de paramètre 1, pour n grand. Cela illustre le paradigme de Poisson[1], selon lequel une somme d'un grand nombre de variables de Bernoulli de petit paramètre, peu corrélées, suit approximativement la loi de Poisson : N peut être vu comme une telle somme. L'écriture de N comme somme de variables de Bernoulli permet un calcul rapide de l'espérance et de la variance de N, ce que l'expression explicite de la loi de N, donnée ci-dessus, ne permet pas.

Note et référence[modifier | modifier le code]

  1. (en) A. D. Barbour, L. Holst et S. Janson, Poisson approximation, The Clarendon Press Oxford University Press,‎ 1992 (ISBN 0198522355).

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :