Principe d'inclusion-exclusion

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 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

$|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

Soient A₁, ..., A_n 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 A_i. On déduit par passage au complémentaire le cardinal de l'ensemble des éléments de E qui n'appartiennent à aucun des A_i :

$\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

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

Inégalités de Bonferroni

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

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.

Démonstration

L'espace probabilisé $\scriptstyle\ (\Omega,\mathcal{A},\mathbb{P})\$ est ici l'ensemble fini $\scriptstyle\ \Omega=\mathfrak{S}_n\$ des permutations de $\scriptstyle\ [\![1,n]\!],\$ muni de la tribu triviale et de la loi uniforme. L'évènement A_k est l'ensemble des permutations laissant l'entier k invariant. Pour une partie S de $\scriptstyle\ [\![1,n]\!],\$ notons A_S l'ensemble des permutations de Ω qui laissent tous les éléments de S invariants. Ainsi

$\bigcup_{i=1}^n A_i\,=\,\left\{N\ge 1\right\}\quad\text{et}\quad A_S=\bigcap_{i\in S} A_i.$

Via l'application qui, à une permutation ω de $\scriptstyle\ \mathfrak{S}_n,\$ associe sa restriction au sous-ensemble $\scriptstyle\ [\![1,n]\!]\backslash S,\$ A_S est en bijection avec l'ensemble des permutations de $\scriptstyle\ [\![1,n]\!]\backslash S,\$ donc le cardinal de A_S est (n-#S)!. Par conséquent, la probabilité de A_S est (n-#S)!/(n!). La formule d'inclusion-exclusion, sous sa forme probabiliste, s'écrit alors

$\mathbb{P}\left(\,N\ge1\right)=\sum_{S\subset[\![1,n]\!],\,S\neq\varnothing} (-1)^{1+\# S}\ \mathbb{P}\left(A_S\right).$

En regroupant les $\scriptstyle\ {n\choose k}\$ parties S de même cardinal k, puisque la probabilité de A_S ne dépend que du cardinal de S, on obtient

$\mathbb{P}\left(\,N\ge1\right)=\sum_{k=1}^n (-1)^{k+1}\ {n\choose k}\frac{n-k!}{n!}\ =\ \sum_{k=1}^n \ \frac{(-1)^{k+1}}{k!},$

puis

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

Notons d_n cette dernière probabilité, qui est la probabilité qu'une permutation de $\scriptstyle\ \mathfrak{S}_n\$ soit un dérangement : d_n est obtenu en tronquant le développement en série de 1/e juste après le terme d'indice n (ce qui, entre parenthèses, est une manière, parmi d'autres, de justifier la convention d₀=1 ). Pour une partie S de $\scriptstyle\ [\![1,n]\!],\$ notons B_S l'ensemble des permutations de Ω dont l'ensemble des points fixes est exactement S : B_S est en bijection avec l'ensemble des dérangements de $\scriptstyle\ [\![1,n]\!]\backslash S,\$ donc le cardinal de B_S est (n-#S)! d_n-#S. Ainsi

$\mathbb{P}\left(\,N=k\right)=\sum_{\#S=k} \mathbb{P}\left(\,B_S\right)\ =\ {n\choose k} \ \frac{n-k!\,d_{n-k}}{n!}\ =\ \frac{d_{n-k}}{k!}\ \simeq\ \frac{e^{-1}}{k!}.$

Or, par définition, une variable aléatoire X suit la loi de Poisson de paramètre a, si, pour tout k entier positif ou nul,

$\mathbb{P}\left(\,X=k\right)= \frac{a^k\,e^{-a}}{k!}.$

Le nombre de dérangements de A est le nombre entier le plus proche de n!/e grâce à une majoration (en valeur absolue) du reste d'une série alternée par le premier terme de ce reste, dans le cas où les valeurs absolues des termes d'une série alternée forment une suite décroissante.

Voir aussi

Notes

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

Pages liées

• Loi de Bernoulli
• Loi de Poisson