Principe d'inclusion-exclusion de Moivre
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Exemple d'inclusion-exclusion à partir de trois ensembles
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 satisfait l’une ou l’autre propriétés données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.), en fonction du nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de ses éléments qui satisfont à la fois certaines de ses propriétés.

Il doit son nom au mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son...) Abraham de Moivre.

Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à...)

Soit E un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers...), 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}.

Cas particulier

Considérons le cas particulier où n=2. Soit E un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) fini, dont chaque élément peut ou non satisfaire l’une ou l’autre des deux propriétés P1 et P2. Notons

  • N1 le nombre d’éléments de E qui vérifient P1,
  • N2 le nombre d’éléments de E qui vérifient P2,
  • N1,2 le nombre d’éléments de E qui vérifient à la fois P1 et P2.

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

N = N1 + N2N1,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.

Exemple

Parmi 20 étudiants, 10 étudient les mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les...), 11 étudient la physique (La physique (du grec φυσις, la nature) est étymologiquement la « science de la nature ». Dans...), 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 (Les diagrammes de Venn et les diagrammes d'Euler sont des représentations schématiques d'ensembles, de relations logiques ou mathématiques.).

image: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.

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é (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet...) ou dans la formule d'inversion de Möbius.

Page générée en 0.026 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique