Prinzip der Inklusion-Exklusion

Seien $A_{1}, \dots, A_{n}$ endliche Mengen. Dann gilt

| ⋃_{i = 1}^{n} A_{i} | = \sum_{r = 1}^{n} ((- 1)^{r - 1} \sum_{1 \leq i_{1} < i_{2} < \dots < i_{r} \leq n} | ⋂_{j = 1}^{r} A_{i_{j}} |) .

Anschaulich:

zunächst werden die Größen aller Mengen addiert,
dann werden die paarweisen Schnitte abgezogen,
danach werden die dreifachen Schnitte wieder addiert,
usw. abwechselnd mit Minus und Plus.

Spezialfall für zwei Mengen

Für endliche Mengen $A, B$ gilt

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

Spezialfall für drei Mengen

Für endliche Mengen $A, B, C$ gilt

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

Beweis

Beweisidee: Wir zeigen, dass jedes Element genau dann auf der rechten Seite genau einmal gezählt wird, wenn es in $⋃_{i = 1}^{n} A_{i}$ liegt.

Sei dazu $a$ ein beliebiges Element.

Falls $a \notin ⋃_{i = 1}^{n} A_{i}$ , dann liegt $a$ in keiner der Mengen $A_{1}, \dots, A_{n}$ und somit auch in keinem Schnitt. Also wird $a$ auf der rechten Seite $0$ -mal gezählt.
Sei nun $a \in ⋃_{i = 1}^{n} A_{i}$ und $a$ liege in genau $m$ der Mengen $A_{1}, \dots, A_{n}$ .

Dann wird $a$ in den Summanden der Ordnung $r$ genau $(\binom{m}{r})$ -mal gezählt, denn man muss genau $r$ der $m$ Mengen auswählen, in denen $a$ liegt. Insgesamt wird $a$ also$$
\sum_{r=1}^{n} (-1)^{r-1} \binom{m}

m a l g e z ä h l t . F ü r $ r > m $ g i l t $ (\binom{m}{r}) = 0 $, a l s o i s t d i e s g l e i c h $ $ \sum_{r = 1}^{m} (- 1)^{r - 1} (\binom{m}{r}) .

Mit dem binomischen Lehrsatz gilt$$\sum_{r=0}^{m} \binom{m}{r} (-1)^r = (1-1)^m = 0.$$Daraus folgt

\sum_{r = 1}^{m} (- 1)^{r - 1} (\binom{m}{r}) = 1.

Also wird jedes Element $a \in ⋃_{i = 1}^{n} A_{i}$ auf der rechten Seite genau einmal gezählt.
Damit zählen linke und rechte Seite genau dieselben Elemente, also gilt

| ⋃_{i = 1}^{n} A_{i} | = \sum_{r = 1}^{n} ((- 1)^{r - 1} \sum_{1 \leq i_{1} < i_{2} < \dots < i_{r} \leq n} | ⋂_{j = 1}^{r} A_{i_{j}} |) .

$◻$

Spezialfall für zwei Mengen

Spezialfall für drei Mengen

Beweis

Links