Inklusion-Exklusion

Studium

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq I \subseteq \{1, \ldots, n\}} (-1)^{|I|+1} \left|\bigcap_{i \in I} A_i\right|

Voraussetzung: $A_1, \ldots, A_n$ $endliche$ $Mengen$ $,$ $n \geq 1$

$A_1, \ldots, A_n$: endliche Mengen
$I$: nichtleere Auswahl von Indizes, über die geschnitten wird
$|I|$: Anzahl der ausgewählten Mengen; sie bestimmt das Vorzeichen
$|M|$: Mächtigkeit, also Anzahl der Elemente einer Menge M

Die Größe einer Vereinigung erhält man, indem man Schnitte ungerader Ordnung addiert und Schnitte gerader Ordnung abzieht.

Erklärung

Das Prinzip von Inklusion und Exklusion zählt die Elemente einer Vereinigung, wenn sich die Mengen überschneiden. Addiert man nur $|A_1| + \ldots + |A_n|$ , werden Elemente in Überschneidungen mehrfach gezählt. Das korrigiert man abwechselnd: Paarschnitte abziehen, Dreierschnitte wieder addieren und so weiter.

Für zwei und drei Mengen:

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

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

Warum jedes Element genau einmal gezählt wird: Liegt $x$ in genau $r \geq 1$ der Mengen, so trägt es $\binom{r}{1} - \binom{r}{2} + \ldots \pm \binom{r}{r} = 1$ bei, denn die alternierende Summe aller $\binom{r}{j}$ ist $0$ .

Oft zählt man das Gegenteil: Die Anzahl der Elemente der Grundmenge, die in keiner der Mengen liegen, ist $|\Omega| - |A_1 \cup \ldots \cup A_n|$ . So entstehen die Formel für die φ-Funktion und die Anzahl fixpunktfreier Permutationen. Für Wahrscheinlichkeiten gilt dieselbe Formel mit $P$ statt $|\cdot|$ .

Beispiele

Wie viele Zahlen von $1$ bis $100$ sind durch $2$ , $3$ oder $5$ teilbar? Durch $d$ teilbar sind $\lfloor 100/d \rfloor$ Zahlen; ein Schnitt entspricht Teilbarkeit durch das Produkt:

50 + 33 + 20 - 16 - 10 - 6 + 3 = 74

Also sind $100 - 74 = 26$ Zahlen zu $30$ teilerfremd.

Umfrage: Von $30$ Studierenden sprechen $18$ Englisch, $12$ Französisch und $9$ Spanisch. $5$ sprechen Englisch und Französisch, $4$ Englisch und Spanisch, $3$ Französisch und Spanisch, $2$ alle drei. Mindestens eine Sprache sprechen

18 + 12 + 9 - 5 - 4 - 3 + 2 = 29,

genau $30 - 29 = 1$ Person spricht keine der drei Sprachen.

Typische Fehler

Nur die Paarschnitte abziehen. Bei drei Mengen werden Elemente im Dreierschnitt dreimal addiert und dreimal abgezogen. Ohne $+|A \cap B \cap C|$ fehlen sie ganz.
Falsches Vorzeichen. Schnitte aus einer ungeraden Anzahl von Mengen werden addiert, aus einer geraden Anzahl abgezogen.
Schnitte mit „genau“ verwechseln. $|A \cap B|$ enthält auch die Elemente, die zusätzlich in $C$ liegen. Wer „nur Englisch und Französisch“ einsetzt ( $5 - 2 = 3$ ), erhält ein falsches Ergebnis.

Inklusion-Exklusion