Une formule combinatoire qui donne la cardinalité d'une réunion finie d'ensembles comme une somme alternée des tailles de toutes les intersections non vides de ces ensembles.

Principe

Compter la réunion en ajoutant et en soustrayant alternativement les tailles des intersections pour corriger exactement le double ou multiple comptage dû aux recouvrements.

Démonstration

Pour deux ensembles A et B, |A ∪ B| = |A| + |B| − |A ∩ B| ; pour trois ensembles A,B,C, |A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B|−|A∩C|−|B∩C| + |A∩B∩C|.

Mauvaise application

Appliquer la formule d'inclusion–exclusion finie à des familles infinies sans étudier la convergence, ou ne soustraire que les intersections par paires alors que des recouvrements d'ordre supérieur existent, ce qui conduit à des comptes erronés.

Conséquence

Appliqué correctement à une famille finie, il donne le nombre exact d'éléments distincts de la réunion et permet des calculs de probabilité rigoureux pour les unions d'événements.

Inversion

L'inversion de Möbius sur le treillis des parties inverse la relation d'inclusion–exclusion, exprimant les tailles d'intersection à partir des tailles d'union ou l'inverse.

Limite

Nécessite un nombre fini d'ensembles ou un contrôle des séries alternées infinies ; il n'est pas directement applicable aux espaces non dénombrables sans justification mesurable.

Tension sémantique

Concurrence avec des heuristiques plus simples (par ex. négliger les recouvrements) ou avec l'utilisation d'indicatrices et de la linéarité de l'espérance ; la tension est entre correction exacte et méthodes approximatives ou probabilistes.

Synthèse

L'inclusion–exclusion est le mécanisme combinatoire exact qui corrige le surcomptage par contributions alternées de toutes les intersections ; c'est le pendant discret de l'inversion de Möbius sur le treillis des sous-ensembles.