Principe d’inclusion–exclusion

Le principe d’inclusion–exclusion est une technique de comptage qui étend la méthode d’addition. Il est utilisé lorsque deux ou plusieurs ensembles se chevauchent et que nous devons éviter de compter les mêmes éléments plusieurs fois.

 

L’idée est que nous additionnons d’abord les ensembles, puis nous soustrayons les éléments qui se chevauchent. S’il y a plusieurs ensembles, il peut être nécessaire d’additionner et de soustraire plusieurs fois.

 

 

Exemple 1: Livres

Une librairie a :

 

• 20 livres de mathématiques
• 15 livres de physique
• 5 livres qui comptent pour les deux

 

Si nous additionnons simplement :

 

$$ \large 20 + 15 = 35 $$

 

nous obtenons trop, car les 5 livres communs sont comptés deux fois. Le nombre correct est :

 

$$ \large 20 + 15 - 5 = 30 $$

 

 

Exemple 2: Étudiants

Il y a 40 étudiants qui suivent les mathématiques, 30 qui suivent la physique et 10 qui suivent les deux matières. Combien d’étudiants uniques y a-t-il ?

 

Ici, nous utilisons la formule :

 

$$ \large |M \cup F| = |M| + |F| - |M \cap F| $$

 

En nombres :

 

$$ \large 40 + 30 - 10 = 60 $$

 

 

Formule

Pour deux ensembles :

 

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

 

Pour trois ensembles :

 

$$ \large |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $$

 

En général, nous alternons entre addition et soustraction, selon combien d’ensembles se chevauchent.

 

 

Quand peut-on utiliser le principe d’inclusion–exclusion ?

 

• Lorsque deux ou plusieurs ensembles se chevauchent.
• Lorsque l’on veut trouver le nombre d’éléments uniques sans double comptage.
• Lorsque les problèmes ne peuvent pas être résolus avec la méthode d’addition seule.

 

 

Résumé

Le principe d’inclusion–exclusion est utilisé pour corriger les chevauchements entre ensembles. Nous additionnons d’abord puis nous soustrayons les éléments qui se chevauchent. Avec plusieurs ensembles, nous alternons entre plus et moins selon le nombre d’ensembles qui se chevauchent.

 

Le principe est un outil important en combinatoire et en probabilité, car il garantit que chaque possibilité unique est comptée exactement une fois.