Principe d'inclusion-exclusion
Le principe d'inclusion-exclusion est une méthode fondamentale de dénombrement permettant de calculer le nombre d'éléments appartenant à l'union de plusieurs ensembles. Il corrige les comptages multiples qui apparaissent lorsqu'un même élément appartient simultanément à plusieurs ensembles.
Lorsqu'on additionne directement les cardinalités de plusieurs ensembles, les éléments communs sont comptés plusieurs fois. Le principe d'inclusion-exclusion consiste donc à soustraire les intersections comptées en trop, puis à réintroduire certaines intersections qui auraient été soustraites trop souvent. Les additions et les soustractions alternent ainsi selon le nombre d'ensembles considérés.
Cette méthode intervient en combinatoire, en probabilités, en théorie des nombres, dans l'analyse des algorithmes, les bases de données, la recherche d'informations, le traitement des doublons et le calcul du nombre de configurations respectant plusieurs contraintes.
Problème du double comptage
Considérons deux ensembles :
| A |
et :
| B |
Pour compter les éléments appartenant à au moins l'un de ces ensembles, on pourrait commencer par calculer :
| |A| + |B| |
Cependant, chaque élément appartenant à l'intersection :
| A ∩ B |
est compté une première fois dans **A** et une deuxième fois dans B.
Il faut donc soustraire une occurrence de chaque élément commun.
On obtient :
|
|A ∪ B| = |A| + |B| - |A ∩ B| |
Principe pour deux ensembles
Pour deux ensembles finis A et B, le principe d'inclusion-exclusion s'écrit :
|
|A ∪ B| = |A| + |B| - |A ∩ B| |
La formule comprend trois étapes :
- inclure tous les éléments de A ;
- inclure tous les éléments de B ;
- exclure une fois les éléments appartenant simultanément à A et à B.
Le terme inclusion-exclusion provient précisément de cette alternance entre l'ajout et le retrait des cardinalités.
Exemple avec deux ensembles
Dans un groupe de 50 programmeurs :
- 30 connaissent Java ;
- 25 connaissent Python ;
- 12 connaissent les deux langages.
On définit :
|
A = ensemble des programmeurs connaissant Java |
et :
|
B = ensemble des programmeurs connaissant Python |
Le nombre de programmeurs connaissant au moins un des deux langages est :
|
|A ∪ B| = |A| + |B| - |A ∩ B| |
Donc :
|
|A ∪ B| = 30 + 25 - 12 |
soit :
| |A ∪ B| = 43 |
Vérification du double comptage
L'addition directe donne :
| 30 + 25 = 55 |
Les 12 programmeurs connaissant les deux langages ont été comptés deux fois.
En soustrayant ces 12 doublons :
| 55 - 12 = 43 |
chaque personne est finalement comptée exactement une fois.
Nombre d'éléments n'appartenant à aucun ensemble
Lorsque l'ensemble universel **U** est connu, le nombre d'éléments n'appartenant ni à A ni à B est :
| |U| - |A ∪ B| |
Dans l'exemple précédent, le groupe contient 50 programmeurs et 43 connaissent au moins Java ou Python.
Le nombre de programmeurs ne connaissant aucun de ces deux langages est donc :
| 50 - 43 = 7 |
Complément de l'union
D'après les lois de De Morgan :
|
(A ∪ B)c = Ac ∩ Bc |
Les éléments n'appartenant ni à A ni à B appartiennent donc au complément de leur union.
On obtient :
|
|(A ∪ B)c| = |U| - |A ∪ B| |
Cette forme est fréquemment utilisée dans les problèmes demandant de compter des objets qui ne satisfont aucune des propriétés données.
Nombre d'éléments appartenant uniquement à A
Le nombre d'éléments appartenant à A, mais pas à B, est :
|
|A \ B| = |A| - |A ∩ B| |
Dans l'exemple des langages :
| 30 - 12 = 18 |
Ainsi, 18 programmeurs connaissent Java sans connaître Python.
Nombre d'éléments appartenant uniquement à B
De manière analogue :
|
|B \ A| = |B| - |A ∩ B| |
Dans l'exemple :
| 25 - 12 = 13 |
Ainsi, 13 programmeurs connaissent Python sans connaître Java.
Décomposition de l'union de deux ensembles
L'union peut être divisée en trois régions disjointes :
| A \ B |
| A ∩ B |
| B \ A |
Sa cardinalité peut donc être calculée par :
|
|A ∪ B| = |A \ B| + |A ∩ B| + |B \ A| |
Dans l'exemple :
| 18 + 12 + 13 = 43 |
Cette décomposition permet de vérifier le résultat obtenu par inclusion-exclusion.
Principe pour trois ensembles
Pour trois ensembles A, B et C, la formule devient :
|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| |
Cette formule alterne les additions et les soustractions :
- les ensembles individuels sont ajoutés ;
- les intersections de deux ensembles sont soustraites ;
- l'intersection des trois ensembles est ajoutée.
Pourquoi réintroduire l'intersection triple ?
Lorsqu'on additionne :
| |A| + |B| + |C| |
un élément appartenant simultanément aux trois ensembles est compté trois fois.
Lorsqu'on soustrait :
|
|A ∩ B| + |A ∩ C| + |B ∩ C| |
ce même élément est ensuite soustrait trois fois.
Son nombre total d'occurrences devient donc :
| 3 - 3 = 0 |
Il faut le réintroduire une fois en ajoutant :
| |A ∩ B ∩ C| |
On obtient finalement :
| 3 - 3 + 1 = 1 |
L'élément est ainsi compté exactement une fois.
Exemple avec trois ensembles
Dans une entreprise de 100 employés :
- 45 utilisent Windows ;
- 40 utilisent Linux ;
- 30 utilisent macOS ;
- 18 utilisent Windows et Linux ;
- 12 utilisent Windows et macOS ;
- 10 utilisent Linux et macOS ;
- 5 utilisent les trois systèmes.
Le nombre d'employés utilisant au moins un de ces systèmes est :
|
45 + 40 + 30 - 18 - 12 - 10 + 5 |
On obtient :
| 115 - 40 + 5 = 80 |
Ainsi :
| |W ∪ L ∪ M| = 80 |
Employés n'utilisant aucun des trois systèmes
L'entreprise compte 100 employés et 80 utilisent au moins un des trois systèmes.
Le nombre d'employés n'utilisant aucun de ces systèmes est donc :
| 100 - 80 = 20 |
Intersection de deux ensembles seulement
Dans une formule à trois ensembles, la valeur :
| |A ∩ B| |
inclut généralement les éléments appartenant également à C.
Pour obtenir le nombre d'éléments appartenant à A et à B, mais pas à C, il faut calculer :
|
|A ∩ B seulement| = |A ∩ B| - |A ∩ B ∩ C| |
Dans l'exemple :
| 18 - 5 = 13 |
Ainsi, 13 employés utilisent Windows et Linux, mais pas macOS.
Éléments appartenant uniquement à A
Pour trois ensembles, le nombre d'éléments appartenant uniquement à A est :
|
|A seulement| = |A| - |A ∩ B| - |A ∩ C| + |A ∩ B ∩ C| |
L'intersection triple doit être ajoutée, car elle a été soustraite deux fois.
Dans l'exemple de l'entreprise :
| 45 - 18 - 12 + 5 = 20 |
Ainsi, 20 employés utilisent uniquement Windows.
Éléments appartenant exactement à deux ensembles
Le nombre d'éléments appartenant exactement à deux des trois ensembles est :
|
|A ∩ B| + |A ∩ C| + |B ∩ C| - 3|A ∩ B ∩ C| |
La multiplication par 3 est nécessaire, car l'intersection triple apparaît dans chacune des trois intersections doubles.
Dans l'exemple :
| 18 + 12 + 10 - 3 × 5 |
donne :
| 40 - 15 = 25 |
Ainsi, 25 employés utilisent exactement deux systèmes.
Éléments appartenant à au moins deux ensembles
Le nombre d'éléments appartenant à au moins deux ensembles comprend :
- les éléments appartenant exactement à deux ensembles ;
- les éléments appartenant aux trois ensembles.
On peut écrire :
|
Nombre appartenant à au moins deux ensembles = |A ∩ B| + |A ∩ C| + |B ∩ C| - 2|A ∩ B ∩ C| |
L'intersection triple est comptée trois fois dans la somme initiale, mais elle doit être conservée une seule fois. Il faut donc la soustraire deux fois.
Dans l'exemple :
|
18 + 12 + 10 - 2 × 5 = 30 |
Éléments appartenant exactement à un ensemble
Le nombre d'éléments appartenant exactement à un des trois ensembles est :
|
|A| + |B| + |C| - 2( |A ∩ B| + |A ∩ C| + |B ∩ C| ) + 3|A ∩ B ∩ C| |
Cette formule peut également être obtenue en calculant séparément les régions appartenant uniquement à A, uniquement à B et uniquement à C.
Formule générale
Pour des ensembles finis :
| A1, A2, ..., An |
le principe général d'inclusion-exclusion est :
|
|A1 ∪ A2 ∪ ... ∪ An| = ∑ |Ai| - ∑ |Ai ∩ Ai| + ∑ |Ai ∩ Ai ∩ Ak| - ... + (-1)n+1 |A1 ∩ A2 ∩ ... ∩ An| |
Les termes sont regroupés selon le nombre d'ensembles présents dans chaque intersection.
Formulation par sous-ensembles d'indices
La formule générale peut être écrite de manière compacte :
|
|⋃i=1n Ai| = ∑∅≠I⊆{1,...,n} (-1)^|I|+1 | ⋂i∈I Ai | |
Dans cette expression :
- I représente un sous-ensemble non vide des indices ;
- |I| représente le nombre d'ensembles dans l'intersection ;
- le signe dépend de la parité de |I|.
Lorsque |I| est impair, le terme est ajouté. Lorsqu'il est pair, il est soustrait.
Alternance des signes
Le principe suit l'ordre suivant :
|
Intersections de 1 ensemble : addition |
|
Intersections de 2 ensembles : soustraction |
|
Intersections de 3 ensembles : addition |
|
Intersections de 4 ensembles : soustraction |
et ainsi de suite.
Le signe d'une intersection de k ensembles est :
| (-1)k+1 |
Principe d'inclusion-exclusion pour quatre ensembles
Pour quatre ensembles A, B, C et D :
|
|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| |
|
- ( |A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D| ) |
|
+ ( |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| ) |
|
- |A ∩ B ∩ C ∩ D| |
Le nombre de termes augmente rapidement avec le nombre d'ensembles.
Nombre de termes de la formule
Pour n ensembles, chaque sous-ensemble non vide des ensembles initiaux produit une intersection dans la formule.
Le nombre total de termes est donc :
| 2n - 1 |
Par exemple :
| Nombre d'ensembles | Nombre de termes |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 10 | 1 023 |
Cette croissance exponentielle constitue l'une des principales limites de l'application directe du principe.
Démonstration par contribution individuelle
Le principe peut être démontré en observant la contribution d'un élément particulier.
Supposons qu'un élément x appartienne exactement à r des ensembles considérés.
Il est compté :
| C(r,1) |
fois dans les ensembles individuels.
Il est ensuite soustrait :
| C(r,2) |
fois dans les intersections doubles.
Il est ajouté :
| C(r,3) |
fois dans les intersections triples, et ainsi de suite.
Sa contribution totale est :
|
C(r,1) - C(r,2) + C(r,3) - ... + (-1)r+1C(r,r) |
Utilisation du binôme de Newton
D'après le binôme de Newton :
|
(1-1)r = ∑k=0r (-1)kC(r,k) |
Comme :
| (1-1)r = 0 |
on obtient :
|
1 - C(r,1) + C(r,2) - ... + (-1)rC(r,r) = 0 |
En réorganisant :
|
C(r,1) - C(r,2) + ... + (-1)r+1C(r,r) = 1 |
Chaque élément appartenant à au moins un ensemble est donc compté exactement une fois.
Forme complémentaire
Le principe d'inclusion-exclusion est souvent utilisé pour compter les éléments qui n'appartiennent à aucun ensemble.
Si U est l'ensemble universel, alors :
|
| U \ (A1 ∪ A2 ∪ ... ∪ An) | = |U| - |A1 ∪ A2 ∪ ... ∪ An| |
En remplaçant l'union par la formule d'inclusion-exclusion :
|
Aucun = |U| - ∑|Ai| + ∑|Ai ∩ Ai| - ∑|Ai ∩ Ai ∩ Ak| + ... |
Cette formulation est utile pour compter les objets ne violant aucune contrainte.
Dénombrement par propriétés interdites
De nombreux problèmes combinatoires demandent de compter les objets respectant plusieurs règles.
On peut définir :
|
Ai = ensemble des objets violant la règle i |
Les objets valides sont ceux qui n'appartiennent à aucun ensemble interdit.
Le nombre de solutions valides est donc :
|
Nombre total - |A1 ∪ A2 ∪ ... ∪ An| |
Le principe d'inclusion-exclusion permet de calculer cette union.
Exemple avec des entiers divisibles
Combien d'entiers compris entre 1 et 100 sont divisibles par 2 ou par 3 ?
Définissons :
|
A = multiples de 2 |
|
B = multiples de 3 |
Le nombre de multiples de 2 est :
| ⌊100/2⌋ = 50 |
Le nombre de multiples de 3 est :
| ⌊100/3⌋ = 33 |
Les entiers divisibles à la fois par 2 et par 3 sont les multiples de :
| PPCM(2,3) = 6 |
Il y en a :
| ⌊100/6⌋ = 16 |
Le résultat est donc :
| 50 + 33 - 16 = 67 |
Multiples de plusieurs nombres
Pour compter les entiers inférieurs ou égaux à N divisibles par au moins un des nombres :
| d1, d2, ..., dn |
on utilise les plus petits communs multiples.
Pour deux diviseurs :
|
Nombre = ⌊N/d1⌋ + ⌊N/d2⌋ - ⌊N/PPCM(d1,d2)⌋ |
Pour trois diviseurs, on ajoute les multiples individuels, on soustrait ceux des PPCM deux à deux, puis on ajoute ceux du PPCM des trois nombres.
Exemple avec trois diviseurs
Combien d'entiers de 1 à 100 sont divisibles par 2, par 3 ou par 5 ?
On définit :
|
A2 = multiples de 2 |
|
A3 = multiples de 3 |
|
A5 = multiples de 5 |
Les cardinalités individuelles sont :
|
|A2| = 50 |A3| = 33 |A5| = 20 |
Les intersections doubles sont :
|
|A2 ∩ A3| = ⌊100/6⌋ = 16 |
|
|A2 ∩ A5| = ⌊100/10⌋ = 10 |
|
|A3 ∩ A5| = ⌊100/15⌋ = 6 |
L'intersection triple est :
|
|A2 ∩ A3 ∩ A5| = ⌊100/30⌋ = 3 |
Ainsi :
|
50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 |
Il existe donc 74 entiers divisibles par au moins l'un des nombres 2, 3 ou 5.
Fonction indicatrice
Le principe d'inclusion-exclusion peut être exprimé à l'aide de fonctions indicatrices.
Pour un ensemble A, la fonction indicatrice est :
|
1_A(x) = 1 si x ∈ A 0 sinon |
L'indicatrice de l'union de deux ensembles vérifie :
|
1_(A∪B)(x) = 1_A(x) + 1_B(x) - 1_(A∩B)(x) |
En additionnant cette égalité pour tous les éléments de l'univers, on retrouve la formule des cardinalités.
Forme générale avec fonctions indicatrices
Pour plusieurs ensembles :
|
1_(A1∪...∪An)(x) = ∑ 1_Ai(x) - ∑ 1_(Ai∩Ai)(x) + ... |
Cette interprétation montre que la formule agit localement sur chaque élément avant d'être additionnée globalement.
Elle est utile en probabilités, en analyse combinatoire et dans certaines démonstrations algébriques.
Inclusion-exclusion en probabilités
Le principe s'applique également aux probabilités.
Pour deux événements A et B :
|
P(A ∪ B) = P(A) + P(B) - P(A ∩ B) |
Pour trois événements :
|
P(A ∪ B ∪ C) = P(A) + P(B) + P(C) - P(A ∩ B) - P(A ∩ C) - P(B ∩ C) + P(A ∩ B ∩ C) |
Les mêmes règles de comptage s'appliquent, car une probabilité est une mesure additive sur des événements disjoints.
Exemple probabiliste
Un programme reçoit deux types d'erreurs :
- une erreur réseau avec une probabilité de 0,20 ;
- une erreur de fichier avec une probabilité de 0,15 ;
- les deux erreurs simultanément avec une probabilité de 0,05.
La probabilité qu'au moins une erreur se produise est :
| 0,20 + 0,15 - 0,05 |
soit :
| 0,30 |
La probabilité qu'aucune erreur ne se produise est donc :
| 1 - 0,30 = 0,70 |
Formule de Bonferroni
Lorsque toutes les intersections sont difficiles à calculer, on peut arrêter la formule avant la fin afin d'obtenir une borne.
Pour des ensembles A1, ..., An :
|
|⋃Ai| ≤ ∑|Ai| |
Cette relation est appelée la borne de l'union.
En ajoutant les intersections doubles :
|
|⋃Ai| ≥ ∑|Ai| - ∑|Ai ∩ Ai| |
Les sommes partielles d'ordre impair donnent généralement une borne supérieure, tandis que celles d'ordre pair donnent une borne inférieure.
Ces résultats sont connus comme les inégalités de Bonferroni.
Borne de l'union
La borne de l'union indique :
|
P(A1 ∪ A2 ∪ ... ∪ An) ≤ P(A1) + P(A2) + ... + P(An) |
Elle ignore les intersections et peut donc surestimer la probabilité réelle.
Cette borne est fréquemment utilisée lorsque les intersections sont inconnues ou trop difficiles à calculer.
Dérangements
Un dérangement est une permutation dans laquelle aucun élément ne conserve sa position initiale.
Pour compter les dérangements de **n** éléments, on définit :
|
Ai = ensemble des permutations dans lesquelles l'élément i reste à sa position |
Le nombre recherché est celui des permutations n'appartenant à aucun des ensembles Ai.
Formule des dérangements
Le nombre de dérangements, noté :
| !n |
ou :
| Dn |
est :
|
Dn = n! ∑k=0n (-1)k/k! |
Sous forme développée :
|
Dn = n! ( 1 - 1/1! + 1/2! - 1/3! + ... + (-1)n/n! ) |
Cette formule constitue une application classique du principe d'inclusion-exclusion.
Exemple de dérangement
Pour trois éléments :
|
A B C |
les permutations sont :
|
ABC ACB BAC BCA CAB CBA |
Les dérangements sont :
|
BCA CAB |
On obtient donc :
| D3 = 2 |
La formule donne :
|
D3 = 3! ( 1 - 1 + 1/2 - 1/6 ) |
soit :
| D3 = 2 |
Approximation des dérangements
Le nombre de dérangements est proche de :
| n!/e |
Plus précisément :
|
Dn = arrondi(n!/e) |
pour tout entier naturel positif n.
La proportion de permutations dans lesquelles aucun élément ne reste à sa place tend donc vers :
| 1/e |
lorsque n devient grand.
Fonction indicatrice d'Euler
Le principe d'inclusion-exclusion permet de calculer la fonction indicatrice d'Euler :
| φ(n) |
Cette fonction compte les entiers compris entre 1 et n qui sont premiers avec n.
Si les facteurs premiers distincts de n sont :
| p1, p2, ..., pk |
alors :
|
φ(n) = n ( 1 - 1/p1 ) ( 1 - 1/p2 ) ... ( 1 - 1/pk ) |
Déduction de la formule d'Euler
Parmi les entiers de 1 à n, on élimine :
- les multiples de p1 ;
- les multiples de p2 ;
- et ainsi de suite.
Les nombres divisibles par plusieurs facteurs premiers ont été éliminés plusieurs fois. Le principe d'inclusion-exclusion corrige ces suppressions multiples.
Pour deux facteurs premiers distincts p et q :
|
φ(n) = n - n/p - n/q + n/(pq) |
Cette expression se factorise en :
|
φ(n) = n(1-1/p)(1-1/q) |
Crible de nombres premiers
Le principe d'inclusion-exclusion est lié aux méthodes de criblage.
Pour compter approximativement ou exactement des entiers ne possédant aucun facteur premier appartenant à une liste donnée, on peut :
- compter tous les entiers ;
- retirer les multiples de chaque nombre premier ;
- ajouter les multiples communs ;
- poursuivre l'alternance.
Le crible d'Ératosthène effectue une opération apparentée en marquant directement les multiples.
Mots utilisant au moins un symbole particulier
Supposons que l'on souhaite compter les chaînes de longueur n formées sur un alphabet de m symboles et contenant au moins une occurrence d'un symbole donné.
Le nombre total de chaînes est :
| mn |
Les chaînes ne contenant jamais le symbole donné utilisent seulement :
| m-1 |
symboles.
Il y en a :
| (m-1)n |
Le nombre recherché est donc :
| mn - (m-1)n |
Il s'agit d'un cas simple de dénombrement par complément.
Mots contenant tous les symboles
Supposons que l'on souhaite compter les chaînes de longueur n sur un alphabet de m symboles dans lesquelles chaque symbole apparaît au moins une fois.
Pour chaque symbole i, on définit :
|
Ai = ensemble des chaînes ne contenant pas le symbole i |
Le nombre recherché est :
|
mn - C(m,1)(m-1)n + C(m,2)(m-2)n - ... + (-1)mC(m,m)0n |
De manière compacte :
|
∑k=0m (-1)k C(m,k) (m-k)n |
Fonctions surjectives
Une fonction :
| f : A → B |
est surjective lorsque chaque élément de B possède au moins un antécédent.
Supposons que :
| |A| = n |
et :
| |B| = m |
Le nombre total de fonctions de A vers B est :
| mn |
Pour compter les fonctions surjectives, il faut retirer les fonctions qui n'utilisent pas un ou plusieurs éléments du codomaine.
Nombre de fonctions surjectives
Le nombre de fonctions surjectives d'un ensemble de n éléments vers un ensemble de m éléments est :
|
∑k=0m (-1)k C(m,k) (m-k)n |
Cette expression est également égale à :
| m! S(n,m) |
où :
| S(n,m) |
désigne un nombre de Stirling de seconde espèce.
Une surjection n'existe que si :
| n ≥ m |
Exemple de fonctions surjectives
Combien existe-t-il de fonctions surjectives d'un ensemble de 4 éléments vers un ensemble de 2 éléments ?
Le nombre total de fonctions est :
| 24 = 16 |
Il existe deux fonctions constantes qui n'utilisent qu'une seule valeur du codomaine.
Le nombre de fonctions surjectives est donc :
| 16 - 2 = 14 |
La formule générale donne :
|
C(2,0)24 - C(2,1)14 + C(2,2)04 |
soit :
| 16 - 2 = 14 |
Affectations où chaque catégorie est utilisée
Le même raisonnement s'applique lorsqu'on distribue n objets distincts dans m catégories distinctes en exigeant que chaque catégorie reçoive au moins un objet.
Chaque distribution correspond à une fonction surjective.
Le nombre de distributions est donc :
|
∑k=0m (-1)k C(m,k) (m-k)n |
Ce modèle apparaît dans :
- l'affectation de tâches ;
- la répartition de fichiers ;
- la distribution d'utilisateurs ;
- l'utilisation de ressources ;
- les problèmes de coloration.
Inclusion-exclusion dans les bases de données
Dans une base de données, plusieurs requêtes peuvent retourner des lignes communes.
Si une application connaît :
- le nombre de lignes satisfaisant la condition A ;
- le nombre de lignes satisfaisant la condition B ;
- le nombre de lignes satisfaisant les deux conditions ;
elle peut calculer le nombre de lignes satisfaisant au moins une condition par :
|
|A ∪ B| = |A| + |B| - |A ∩ B| |
L'opérateur SQL :
| UNION |
élimine les doublons selon un principe comparable.
UNION et UNION ALL
Dans SQL :
| UNION ALL |
conserve toutes les lignes provenant des deux requêtes, y compris les doublons.
L'opérateur :
| UNION |
retire les doublons du résultat.
Conceptuellement :
| Nombre de lignes distinctes = Nombre de lignes de A + Nombre de lignes de B - Nombre de lignes communes |
La mise en oeuvre réelle dépend toutefois du moteur de base de données.
Inclusion-exclusion dans la recherche d'informations
Lorsqu'un moteur de recherche combine plusieurs critères, certains documents peuvent correspondre à plusieurs conditions.
Par exemple :
|
Documents contenant Java OU Documents contenant Python |
Le nombre total de documents distincts est :
|
Java + Python - Java ET Python |
Cette correction évite de présenter plusieurs fois le même document.
Inclusion-exclusion dans les graphes
Le principe peut être utilisé pour compter :
- les sommets possédant au moins une propriété ;
- les chemins évitant certains sommets ;
- les colorations respectant des contraintes ;
- les couvertures ;
- les objets contenant certains sous-graphes ;
- les configurations interdites.
Il apparaît également dans le calcul du polynôme chromatique d'un graphe et dans certaines méthodes de dénombrement de chemins hamiltoniens.
Inclusion-exclusion et chaînes binaires
Considérons les chaînes binaires de longueur n contenant au moins un 0 et au moins un 1.
Le nombre total de chaînes est :
| 2n |
Les chaînes ne contenant aucun 0 sont constituées uniquement de 1. Il en existe une.
Les chaînes ne contenant aucun 1 sont constituées uniquement de 0. Il en existe également une.
Pour :
| n > 0 |
le nombre recherché est :
| 2n - 2 |
Contraintes de positions
Le principe peut servir à compter les permutations dans lesquelles certaines positions sont interdites.
Pour chaque position interdite i, on définit :
|
Ai = ensemble des permutations utilisant l'affectation interdite i |
Le nombre de permutations valides est :
|
n! - |A1 ∪ A2 ∪ ... ∪ Ak| |
Cette méthode généralise le calcul des dérangements.
Problème des rencontres
Le problème des rencontres considère n lettres et n enveloppes portant chacune une adresse distincte.
Les lettres sont placées aléatoirement dans les enveloppes.
On cherche le nombre de répartitions dans lesquelles aucune lettre n'est placée dans sa propre enveloppe.
Ce nombre est exactement celui des dérangements :
| Dn |
Le principe d'inclusion-exclusion permet de retirer les permutations comportant au moins une correspondance correcte.
Polynôme chromatique
Le polynôme chromatique d'un graphe indique le nombre de colorations propres de ses sommets avec un certain nombre de couleurs.
Une coloration est propre lorsque deux sommets adjacents ne possèdent pas la même couleur.
Pour certains graphes, le principe d'inclusion-exclusion peut être appliqué aux événements :
|
les deux extrémités d'une arête possèdent la même couleur |
On retire alors les colorations violant au moins une contrainte d'adjacence.
Inclusion-exclusion algorithmique
Pour appliquer le principe à n ensembles, un algorithme peut parcourir tous les sous-ensembles non vides des ensembles initiaux.
Chaque sous-ensemble d'indices représente une intersection.
Un masque binaire de **n** bits peut indiquer les ensembles inclus dans l'intersection.
Par exemple, avec quatre ensembles :
| 0101 |
représente l'intersection du premier et du troisième ensemble.
Algorithme général
|
MODULE InclusionExclusion(ensembles) n ← nombre d'ensembles résultat ← 0 POUR masque ← 1 JUSQU'A 2n-1 intersection ← univers nombreEnsembles ← 0 POUR i ← 0 JUSQU'A n-1 SI le bit i de masque vaut 1 ALORS intersection ← intersection ∩ ensembles[i] nombreEnsembles ← nombreEnsembles + 1 FIN SI FIN POUR SI nombreEnsembles est impair ALORS résultat ← résultat + cardinalité(intersection) SINON résultat ← résultat - cardinalité(intersection) FIN SI FIN POUR RETOURNER résultat |
Complexité de l'algorithme général
Il existe :
| 2n - 1 |
sous-ensembles non vides de n ensembles.
Si chaque masque examine les **n** ensembles, la complexité de contrôle est :
| O(n2n) |
À cette complexité s'ajoute le coût du calcul de chaque intersection.
L'application directe devient donc rapidement coûteuse lorsque le nombre d'ensembles augmente.
Optimisation par programmation dynamique
Il est possible de réutiliser certaines intersections déjà calculées.
Pour un masque non nul, on peut retirer l'un de ses bits et construire son intersection à partir d'un masque plus petit.
|
intersection[masque] = intersection[masqueSansUnBit] ∩ ensemble[bitRetiré] |
Cette méthode évite de recalculer chaque intersection entièrement depuis le début.
La consommation mémoire devient cependant proportionnelle au nombre de masques :
| O(2n) |
Algorithme pour compter les multiples
Le principe peut être appliqué sans matérialiser les ensembles.
Pour compter les entiers de 1 à N divisibles par au moins un diviseur donné :
|
MODULE CompterMultiples(N,diviseurs) résultat ← 0 m ← longueur(diviseurs) POUR masque ← 1 JUSQU'A 2m-1 ppcm ← 1 nombreDiviseurs ← 0 POUR i ← 0 JUSQU'A m-1 SI le bit i de masque vaut 1 ALORS ppcm ← PPCM( ppcm, diviseurs[i] ) nombreDiviseurs ← nombreDiviseurs + 1 FIN SI FIN POUR quantité ← N DIV ppcm SI nombreDiviseurs est impair ALORS résultat ← résultat + quantité SINON résultat ← résultat - quantité FIN SI FIN POUR RETOURNER résultat |
Prévention des dépassements
Lors du calcul d'un PPCM :
|
PPCM(a,b) = a/PGCD(a,b) × b |
le produit peut dépasser la capacité du type numérique.
Dans un algorithme de dénombrement limité à **N**, il est souvent inutile de poursuivre lorsqu'un PPCM devient supérieur à N.
On peut alors considérer que :
| N DIV PPCM = 0 |
et interrompre le calcul de cette intersection.
Exemple en Java
- import java.util.HashSet;
- import java.util.List;
- import java.util.Set;
-
- public class InclusionExclusionSample {
-
- public static <T> int cardinaliteUnion(
- List<Set<T>> ensembles
- ) {
- int nombreEnsembles =
- ensembles.size();
-
- if (nombreEnsembles >= 31) {
- throw new IllegalArgumentException(
- "Trop d'ensembles pour un masque int."
- );
- }
-
- long resultat = 0;
- int nombreMasques =
- 1 << nombreEnsembles;
-
- for (
- int masque = 1;
- masque < nombreMasques;
- masque++
- ) {
- Set<T> intersection = null;
- int cardinaliteMasque = 0;
-
- for (
- int i = 0;
- i < nombreEnsembles;
- i++
- ) {
- if (
- (masque & (1 << i)) != 0
- ) {
- cardinaliteMasque++;
-
- if (intersection == null) {
- intersection =
- new HashSet<>(
- ensembles.get(i)
- );
- } else {
- intersection.retainAll(
- ensembles.get(i)
- );
- }
- }
- }
-
- int taille =
- intersection == null
- ? 0
- : intersection.size();
-
- if (
- (cardinaliteMasque & 1) == 1
- ) {
- resultat += taille;
- } else {
- resultat -= taille;
- }
- }
-
- if (
- resultat > Integer.MAX_VALUE
- ||
- resultat < Integer.MIN_VALUE
- ) {
- throw new ArithmeticException(
- "Le résultat dépasse la capacité d'un int."
- );
- }
-
- return (int) resultat;
- }
-
- public static void main(String[] args) {
- Set<Integer> a =
- Set.of(1, 2, 3, 4);
-
- Set<Integer> b =
- Set.of(3, 4, 5, 6);
-
- Set<Integer> c =
- Set.of(4, 6, 7);
-
- int resultat =
- cardinaliteUnion(
- List.of(a, b, c)
- );
-
- System.out.println(
- "Cardinalité de l'union : "
- + resultat
- );
- }
- }
Les ensembles utilisés sont :
| A = {1,2,3,4} |
| B = {3,4,5,6} |
| C = {4,6,7} |
Leur union est :
| {1,2,3,4,5,6,7} |
Le programme affiche donc :
| Cardinalité de l'union : 7 |
Calcul direct ou inclusion-exclusion
Lorsque les ensembles sont explicitement disponibles en mémoire, il est généralement plus simple de construire directement leur union.
Par exemple, avec une table de hachage :
|
résultat ← ensemble vide
POUR CHAQUE ensemble Ajouter tous ses éléments à résultat FIN POUR |
Le principe d'inclusion-exclusion est surtout utile lorsque :
- les ensembles sont trop grands pour être construits ;
- seules leurs cardinalités et celles de leurs intersections sont connues ;
- les ensembles sont définis implicitement ;
- les objets doivent respecter plusieurs contraintes ;
- une formule symbolique est recherchée.
Tableau récapitulatif
| Situation | Formule | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Union de deux ensembles | ` | A | B | - | A∩B | ` | |||||||||
| Union de trois ensembles | ` | A | + | B | + | C | - | A∩B | - | A∩C | - | B∩C | + | A∩B∩C | - |
| Aucun des ensembles | ` | U | - | A1∪...∪An | ` | ||||||||||
| Seulement A parmi deux ensembles | ` | A | - | A∩B | ` | ||||||||||
| Seulement A parmi trois ensembles | ` | A | - | A∩B | - | A∩C | + | A∩B∩C | ` | ||||||
| Exactement deux de trois ensembles | ` | A∩B | + | A∩C | + | B∩C | -3 | A∩B∩C | ` | ||||||
| Au moins deux de trois ensembles | ` | A∩B | + | A∩C | + | B∩C | -2 | A∩B∩C | ` | ||||||
| Nombre de dérangements | `n!∑n=0n(-1)k/k!` | ||||||||||||||
| Nombre de surjections | `∑k=0m(-1)kC(m,k)(m-k)n` |
Applications
Le principe d'inclusion-exclusion est utilisé dans de nombreux domaines :
- dénombrement combinatoire ;
- calcul des probabilités ;
- théorie des ensembles ;
- théorie des nombres ;
- calcul des dérangements ;
- fonctions surjectives ;
- distribution d'objets ;
- bases de données ;
- suppression des doublons ;
- moteurs de recherche ;
- systèmes de filtrage ;
- analyse de contraintes ;
- théorie des graphes ;
- cryptographie ;
- calcul de la fonction d'Euler ;
- cribles de nombres premiers ;
- analyse des événements concurrents ;
- évaluation de la fiabilité des systèmes.
Avantages
Le principe d'inclusion-exclusion présente plusieurs avantages :
- il corrige systématiquement les doubles comptages ;
- il fournit une formule exacte pour l'union de plusieurs ensembles ;
- il permet de compter les objets respectant plusieurs contraintes ;
- il évite parfois l'énumération exhaustive ;
- il s'applique aussi bien aux cardinalités qu'aux probabilités ;
- il permet de calculer le nombre de fonctions surjectives ;
- il fournit une démonstration naturelle de plusieurs formules combinatoires ;
- il peut être combiné avec l'arithmétique modulaire et la théorie des nombres ;
- il permet d'obtenir des bornes lorsque la formule complète est trop coûteuse.
Limites et précautions
Plusieurs précautions doivent être prises :
- les intersections doivent être correctement définies ;
- une intersection double peut inclure les éléments d'intersections plus nombreuses ;
- les signes doivent alterner selon la taille des intersections ;
- l'intersection triple doit être réintroduite dans le cas de trois ensembles ;
- le nombre de termes augmente comme 2n-1 ;
- les calculs deviennent rapidement coûteux pour un grand nombre d'ensembles ;
- les valeurs intermédiaires peuvent être beaucoup plus grandes que le résultat final ;
- des erreurs de dépassement de capacité peuvent survenir ;
- les données fournies doivent être cohérentes entre elles ;
- il ne faut pas confondre « exactement », « au moins » et « seulement » ;
- la construction directe de l'union peut être préférable lorsque les ensembles sont disponibles.
Remarque
Le principe d'inclusion-exclusion transforme un problème de chevauchement entre plusieurs ensembles en une alternance structurée d'additions et de soustractions. Les ensembles individuels sont d'abord inclus, les intersections doubles sont exclues, les intersections triples sont réintroduites, puis l'alternance se poursuit pour les intersections d'ordre supérieur.
Cette méthode permet de garantir que chaque élément appartenant à l'union est finalement compté exactement une fois. En programmation, elle est particulièrement utile lorsque les ensembles sont définis implicitement, lorsque seules leurs cardinalités sont connues ou lorsqu'un problème comporte plusieurs contraintes interdites. Elle prépare naturellement à l'étude des dérangements, des fonctions surjectives, des nombres de Stirling, des probabilités discrètes et des techniques avancées de dénombrement.