Principe d'inclusion-exclusion de Moivre

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Exemple d'inclusion-exclusion à partir de trois ensembles

En combinatoire, le principe d’inclusion-exclusion de Moivre permet d’exprimer le nombre d’éléments qui satisfont à l’une ou l’autre de propriétés données, en fonction des nombres de ces éléments qui satisfont à la fois à certaines de ces propriétés.

Il doit son nom au mathématicien Abraham de Moivre.

[modifier] Théorème

Soit E un ensemble fini, dont chaque élément peut ou non satisfaire certaines de n propriétés $P_1, \ldots, P_n$ . Notons $N_{i_1,\ldots,i_k}$ le nombre d’éléments de E qui vérifient les propriétés $P_{i_1},\ldots,P_{i_k}$ (et éventuellement d’autres propriétés). Alors le nombre N d’éléments (distincts) de E qui satisfont à l’une ou l’autre de ces propriétés est donné par

$\sum_{i_1} N_{i_1} - \sum_{i_1<i_2} N_{i_1,i_2} + \sum_{i_1<i_2<i_3}N_{i_1,i_2,i_3} - \ldots + (-1)^{n-1} N_{1,\ldots,n}.$

De façon équivalente, le nombre d’éléments de E qui ne vérifient aucune propriété est égal à

$N - \sum_{i_1} N_{i_1} + \sum_{i_1<i_2} N_{i_1,i_2} - \sum_{i_1<i_2<i_3}N_{i_1,i_2,i_3} + \ldots + (-1)^{n} N_{1,\ldots,n}.$

[modifier] Cas particulier

Considérons le cas particulier où n=2. Soit E un ensemble fini, dont chaque élément peut ou non satisfaire l’une ou l’autre des deux propriétés $P 1$ et $P 2$ . Notons

$N 1$ le nombre d’éléments de E qui vérifient $P 1$ ,
$N 2$ le nombre d’éléments de E qui vérifient $P 2$ ,
$N 1,2$ le nombre d’éléments de E qui vérifient à la fois $P 1$ et $P 2$ .

Alors le nombre N d’éléments de E qui satisfont à l’une ou l’autre de ces propriétés est égal à

N = N 1 + N 2 - N 1,2

Autrement dit, le nombre d’objets vérifiant l’une ou l’autre de ces deux propriétés est égal à la somme des nombres d’objets vérifiant chaque propriété diminuée du nombre d’objets possédant à la fois les deux propriétés.

[modifier] 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.

[modifier] Applications

Le principe inclut aussi des inégalités, montrant que la somme des premiers termes de la formule est alternativement un majorant et un minorant du premier membre. Ces inégalités peuvent être utilisées dans les cas où la formule complète est trop encombrante.

Le principe d’inclusion-exclusion se retrouve dans la formule du crible de Poincaré et la formule du crible de Poincaré en probabilité ou dans la formule d'inversion de Möbius.