notes/school/di-ma/20181016_1-kombinatorische_prinzipien.md

---
title: Kombinatorische Prinzipien
date: 2018-10-16
---

# Inklusion-Exklusion-Prinzip (Verallgemeinerung der Summenformel)

**Gegeben**: $S_1, ... S_n$ *paarweise disjunkte* Mengen, dann gilt

$$
\vert \bigcup\limits_{i=1}^n S_i \vert = \sum\limits_{i=1}^n \vert S_i \vert
$$

Warum? Jedes Element der Vereinigung liegt in genau einer Teilmenge.

**Frage**: Was passiert, falls $S_i$ nicht disjunkt sind?

**Beispiel**: $n=2$, zwei endliche Mengen $A_1, A_2$ mit $A_1 \cap A_2 \neq \emptyset$

> Hier könnte Ihr Venn Diagramm stehen (zwei sich schneidende Mengen)

Dann gilt

$$
\vert A_1 \cup A_2 \vert = \vert A_1 \vert + \vert A_2 \vert - \vert A_1 \cap A_2 \vert
$$

Wir müssen die Größe des Schnittes abziehen, da diese Elemente doppelt gezählt werden.

**Beispiel**: $n=3$, $A_1, A_2, A_3$ endliche Mengen

> Hier könnte wieder ein Venn Diagramm stehen (drei sich schneidende Meingen)

Dann gilt

$$
\vert A_1 \cup A_2 \cup A_3 \vert = \vert A_1 \vert + \vert A_2 \vert + \vert A_3 \vert - \vert A_1 \cap A_2 \vert  -
	\vert A_1 \cap A_3 \vert - \vert A_2 \cap A_3 \vert + \vert A_1 \cap A_2 \cap A_3 \vert
$$

Allgemein gilt:

## **Satz**: (Inklusion-Exklusion-Prinzip, Siebformel)

Seien $A_1, ... A_n$ endliche mengen, dann gilt:

$$
\vert \bigcup\limits_{i=2}^n A_i \vert = \sum\limits_{r=1}^n (-1)^{r-1}
	\sum\limits_{\substack{I \subseteq \{1,...n\}\\\vert I \vert = r}} \vert \bigcap\limits_{i \in I} A_i \vert
$$
$$
\tag*{$\Box$}
$$

**Beispiel**: $n=2$ anhand der Formel

$$
\vert \bigcup\limits_{i=1}^2 A_i \vert = \vert A_1 \cup A_2 \vert =\\
= \sum\limits_{r=1}^2 (-1)^{r-1} \sum\limits_{\substack{I \subseteq \{1,...n\}\\\vert I \vert = r}}
	\vert \bigcap\limits_{i \in I} A_i \vert \\
= (-1)^0 (\vert \bigcap\limits_{i \in \{1\}} A_i \vert + \vert \bigcap\limits_{i \in \{2\}} A_i \vert)
	+ (-1)^1 (\vert \bigcap\limits_{i \in \{1,2\}} A_i \vert) \\
= (\vert A_1 \vert + \vert A_2 \vert) - \vert A_1 \cap A_2 \vert
$$

## Beweis

Sei $a \in \bigcup\limits_{i=1}^n$. Wir müssen zeigen, dass dieses Element $a$ auf der rechten Seite der Gleichung
insgesamt einmal gezählt wird. Ohne Einschränkung sei
$$
a \in A_i \text{ für } i \in \{1,...t\}
$$
dann gilt für $I \subseteq \{1,...n\}$

$$
a \in \bigcap\limits_{i \in I} A_i \text{ genau dann, wenn } I \subseteq \{1,...t\}
$$

Damit folgt: $a$ wird auf der rechten Seite

$$
\sum\limits_{r=1}^n (-1)^{r-1} \sum\limits_{\substack{I \subseteq \{1,...t\}\\\vert I \vert = r}} 1
$$

mal gezählt. Es gilt

$$
\sum\limits_{\substack{I \subseteq \{1,...t\}\\\vert I \vert = r}} 1 = \binom{t}{r}
$$

und damit

$$
\sum\limits_{r=1}^n (-1)^{r-1} \binom{t}{r} = \sum\limits_{r=1}^t (-1)^{1-r} \binom{t}{r}
$$

Es gilt weiterhin

$$
0 = (-1+1)^t = \sum\limits_{r=0}^t \binom{t}{r} (-1)^r (1)^{t-r} = \\
= 1 + \sum\limits_{r=1}^t \binom{t}{r} (-1)^r \\
= 1 - \sum\limits_{r=1}^t \binom{t}{r} (-1)^{r-1} \\
\Rightarrow \sum\limits_{r=1}^t \binom{t}{r} (-1)^{r-1} = 1
$$
$$
\tag*{$\Box$}
$$

**Beispiel**:

1. **Frage**: Wie viele Zahlen zwischen 1 und 100 sind durch 2 oder 3 oder 5 teilbar?

	Sei $A_k = \{x \in \{1,...100\} \mid k \text{ teilt } x \}$, dann gilt
	$\vert A_k \vert = \left\lfloor \frac{100}{k} \right\rfloor$ und

	$$
	A_k \cap A_l = A_{\text{kgV}(k,l)}
	$$

	Wir müssen $\vert A_2 \cup A_3 \cup A_5 \vert$ bestimmen. Nach Formel

	$$
	\vert A_2 \cup A_3 \cup A_5 \vert = \\
	\vert A_2 \vert + \vert A_3 \vert + \vert A_5 \vert
	- \vert A_2 \cap A_3 \vert - \vert A_2 \cap A_5 \vert - \vert A_3 \cap A_5 \vert
	+ \vert A_2 \cap A_3 \cap A_5 \vert =\\
	= 50 + 33 + 20 - 16 - 10 - 6 + 3 = \\
	= 74
	$$

2. **Frage**: Wie viele Permutationen $\pi : \{1,...n\} \to \{1,...n\}$ gibt es, die keinen Fixpunkt haben, d.h.
	$\forall x \in \{1,...n\}$ gilt $\pi(x) \neq x$?

	Wir zählen stattdessen die Permutationen, die mindestens einen Fixpunkt haben. Wir definieren
	$A_i = \{\pi : \{1,...n\} \to \{1,...n\} \mid \pi(i) = i \}$ für $i \in \{1,...n\}$, d.h. $A_i$ ist die Menge aller
	Permutationen mit Fixpunkt $i$.

	Die Menge aller Permutationen mit mindestens einem Fixpunkt ist $E_n = \bigcup_{i=1}^n A_i$ und es gilt

	$$
	\vert E_n \vert = \vert \bigcup\limits_{i=1}^n A_i \vert = \sum\limits_{r=1}^n (-1)^{r-1}
		\sum\limits_{\substack{I \subseteq \{1,...n\}\\\vert I \vert = r}} \vert \bigcap\limits_{i \in I} A_i \vert
	$$

	Permutationen in $\vert \bigcap\limits_{i \in I} A_i \vert$ für $I \subseteq \{1,...n\}$ mit $\vert I \vert = r$
	haben $r$ Fixpunkte in $i \in I$. Davon gibt es $(n-r)!$ viele Permutationen (Fixpunkte fest; für den ersten
	nicht-Fixpunkt $(n-r)$ Möglichkeiten, für den zweiten nicht-Fixpunkt $(n-r-1)$ Möglichkeiten, ...). Damit folgt

	$$
	\vert E_n \vert = \sum\limits_{r=1}^n (-1)^{r-1} \sum\limits_{\substack{I \subseteq \{1,...n\}\\\vert I \vert = r}}
		(n-r)! = \\
	= \sum\limits_{r=1}^n (-1)^{r-1} (n-r)! \binom{n}{r} \\
	= \sum\limits_{r=1}^n (-1)^{r-1} \frac{n!}{r!} = n! \left (\sum\limits_{r=1}^n \frac{(-1)^{r-1}}{r!} \right )
	$$

	Sei $D_n$ die Menge der Permutationen, die keinen Fixpunkt haben, dann gilt

	$$
	\vert D_n \vert = n! - \vert E_n \vert = n! \left ( 1 - \sum\limits_{r=1}^n (-1)^{r-1} \frac{1}{r!} \right ) = \\
	= n! \left ( 1 + \sum\limits_{r=1}^n (-1)^r \frac{1}{r!} \right ) = \\
	= n! \left ( \sum\limits_{r=0}^n \frac{(-1)^r}{r!} \right )
	$$

$\sum\limits_{r=0}^n \frac{(-1)^r}{r!}$ ist die Wahrscheinlichkeit, dass eine zufällige Permutation keinen Fixpunkt hat.

$$
n \to \infty \\
\sum\limits_{r=0}^n \frac{(-1)^r}{r!} \to e^{-1}
$$


# Doppeltes Abzählen

Seien $S, T$ endliche Mengen und $R \subseteq S \times T$, dann gilt

$$
|R| = \sum\limits_{t \in T} | \{s\in S \mid (s,t) \in R\} | = \text{ "Zeilensumme"} \\
\sum\limits_{s\in S} |\{t\in T \mid (s,t) \in R\} | \text{ "Spaltensumme"}
$$

**Beispiel**: Gegeben seien eine $(n \times m)$ Matrix $M = (a_{ij})$ mit $a_{ij} \in \mathbb{N}$, dann kann man die
Summe aller Einträge berechnen als
$$
\sum\limits_{i=1}^m \left ( \sum\limits_{j=1}^n a_{ij} \right ) =
\sum\limits_{j=1}^n \left ( \sum\limits_{i=1}^m a_{ij} \right )
$$