--- title: Binomialkoeffizient date: 2018-10-10 --- # Wiederholung $n$ Elemente, $k$ mal ziehen: --- | geordnet | ungeordnet :---: | :---: | :---: mit zurücklegen | $n^k$ | $\binom{n+k-1}{k}$ ohne zurücklegen | $n^{\underline{k}}$ | $\binom{n}{k} = \frac{n!}{k!\cdot(n-k)!}$ ## Beispiel a **Frage**: Wie viele 10-elementige Teilmengen von der 100-elementigen Menge $M = \{1,2,...100\}$ 1. gibt es? 2. die entweder die 1 oder die 2 enthalten gibt es? ### Zu 1) $$ \binom{100}{10} $$ ### Zu 2) Zwei Teile: * Die Anzahl der 10 elementingen Teilmengen, die 1 aber nicht 2 enthalten * Die Anzahl der 10 elementingen Teilmengen, die 2 aber nicht 1 enthalten In beiden Fällen gibt es $\binom{98}{9}$ Möglichkeiten. Die Fälle sind disjunkt $\Rightarrow$ es gibt $2 \cdot \binom{98}{9}$ Möglichkeiten ## Beispiel b Wahl mit 100 Wahlberechtigten und 2 Kandidaten. Jede Stimme hat 4 Möglichkeiten (Kandidat 1, Kandidat 2, enthalten oder ungültig). **Frage**: Wie viele Ergebnisse kann es geben? Dies entspricht der Anzahl der 100 elementigen Multimengen einer 4-elementigen Menge $$ \binom{100+4-1}{100} = \binom{103}{100} = 353702 $$ # Eigenschaften von Binomialkoeffizienten **Satz**: Seien $n, k \in \mathbb{N}$ $k \leq n$ dann gilt 1. $\binom{n}{k} = \binom{n}{n-k}$ 2. $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ 3. $\binom{n}{k} = \sum\limits^k_{l=0} \binom{n}{l} \cdot \binom{n}{k-l}$ 4. $(a+b)^n = \sum\limits^n_{k=0} \binom{n}{k} \cdot a^k \cdot b^{n-k}$ ## Beweis Wir wollen kombinatorische Beweise geben. Wir zählen auf beiden Seiten der Gleichung die gleichen Objekte aber auf verschiedene Weise. **zu 1)** Sei $M$ eine $n$-elementige Menge * $\binom{n}{k}$ zählt die $k$-elementigen Teilmengen von $M$ * $\binom{n}{n-k}$ zählt die $(n-k)$-elementigen Teilmengen von $M$ Wir betrachten die Abbildung $$ f: \text{Teilmenge von M} \to \text{Teilmenge von M} \\ f(A) = M \setminus A = \{x \in M \mid x \notin A\} = A^{\mathrm{C}} $$ Es gilt: 1. $\vert A \vert = k \Rightarrow \vert f(A) \vert = n-k$ 2. $f$ ist bijektiv (die Umkehrabbildung ist $f$ selbst) Damit folgt aus dem Gleichheitsprinzip $$ \binom{n}{k} = \binom{n}{n-k} $$ **zu 2)** Sei $M = \{1, ... n\}$ und $\mathbb{T} = \{A \subseteq M \mid \vert A \vert = k\}$ Es gilt $\vert\mathbb{T}\vert = \binom{n}{k}$ Wir teilen die Menge $\mathbb{T}$ auf in zwei disjunkte Teile $$ \mathbb{T}_1 = \{ A \subseteq M \mid \vert A \vert = k, n \notin A\} \\ \mathbb{T}_2 = \{ A \subseteq M \mid \vert A \vert = k, n \in A\} $$ Dann gilt (Summenregel) $$ \binom{n}{k} = \vert \mathbb{T} \vert = \vert \mathbb{T}_1 \vert + \vert \mathbb{T}_2 \vert $$ * $\vert \mathbb{T}_1 \vert = \binom{n-1}{k}$, denn Elemente aus $\mathbb{T}_1$ entsprechen $k$-elementigen Teilmengen aus $M^\prime = \{1,... n-1\}$ * $\vert \mathbb{T}_2 \vert = \binom{n-1}{k-1}$, denn für jedes $A \in \mathbb{T}_2$, d.h. $A \subseteq M, \vert A \vert = k$ und $n \in A$ betrachte $$ A^\prime = A \setminus \{n\} $$ $A^\prime$ ist eine $(k-1)$-elementige Teilmenge von $M^\prime = \{1,... n-1\}$ **zu 3)** Seien $A$, $B$ Mengen mit $\vert A \vert = n$ und $\vert B \vert = m$ mit $A \cap B = \emptyset$ (disjunkt) $\binom{n+m}{k}$ ist die Anzahl der $k$-elementigen Teilmengen von $A \dot\cup B$ ($\vert A \dot\cup B \vert = n + m$). Wir teilen die $k$-elementigen Teilmengen von $A \dot\cup B$ in $k+1$ disjunkte Fälle auf ** hier wäre ein Venn Diagramm. Mach das mal **Fall l** (für $l \in \{0,...k\}$) Betrachte die $k$-elementigen Teilmengen $S$ von $A \cup B$, so dass $\vert A \cap S \vert = l$ ($\Leftrightarrow \vert B \cap S \vert = k - l$), d.h. wir betrachten die Anzahl der $l$-elemeniigen Teilmengen von $A$ und der $(k-l)$-elementigen Teilmenge von $B$. Mit der Produktregel ergeben sich $\binom{n}{l} \cdot \binom{m}{k-l}$. Mit der Summenformel ergibt sich $$ \binom{n+m}{k} = \sum\limits^k_{l=0} \binom{n}{l} \cdot \binom{m}{k-l} $$ **zu 4)** $$ (a+b)^n = (a+b) \cdot (a+b) \cdot ... (a+b) $$ Beim Ausmultiplizieren "entscheiden" wir uns für jede der $n$ Klammern for $a$ oder $b$. Für einen Term $a^k\cdot b^{n-k}$ wählen wir aus den $n$ Klammern genau $k$-mal das $a$. Damit haben wir genau $\binom{n}{k}$ Möglichkeiten den Term $a^k \cdot b^{n-k}$ zu erhalten. # Kombinatorische Prinzipien ## Schubfachprinzip **Beispiel**: Wir haben 9 Schubladen und 10 Objekte, die wir auf die Schubladen verteilen wollen. Dann gibt es eine Schublade, in der mindestens 2 Objekte landen. ### Satz Seien $X$, $Y$ endliche Mengen mit $\vert X \vert \geq \vert Y \vert + 1$ und $f: X \to Y$ eine Abbildung dann $$ \exists y \in Y \text{ so dass } \vert f^{-1}(y) \vert = \vert \{x\in X \mid f(x) = y\} \vert \geq 2 $$ ### Beweis Statt $A \Rightarrow B$ zeigen wir $\lnot B \Rightarrow \lnot A$ Sei $f: X \to Y$ gegeben so dass $\forall y \in Y$ gilt $\vert f^{-1}(y) \vert \leq 1$, dann gilt $$ \vert X \vert = \sum\limits_{y \in Y} \vert f^{-1}(y) \vert \leq \sum\limits_{y \in Y} 1 = \vert Y \vert $$ Allgemeiner gilt: Seien $X$, $Y$ endliche Mengen und $f: X \to Y$ eine Abbildung, dann $\exists y \in Y$ so dass $$ \vert f^{-1}(y) \vert \geq \left\lceil \frac{\vert X \vert}{\vert Y \vert} \right\rceil $$ ($\lceil \cdot \rceil$ ist die obere Gaussklammer, das heißt die kleinste natürliche Zahl größer als $x$). **Beispiel 1**: *Gegeben*: $n$ Personen $1,...n$ mit Bekanntschaftsrelationen, darstellbar als Graph mit Personen als Konten und Kanten zwischen Knoten, falls sich die Personen kennen. ![Personen Graph](./20181010-personen.png) * 1 kennt 4 Personen * 2 kennt 2 Personen * 3 kennt 3 Personen * 4 kennt 2 Personen * 5 kennt 3 Personen Es gibt (mindestens) 2 Personen, die die gleiche Anzahl von Personen kennen. Dies gilt **immer**. ### Satz Unter $n$ Personen gibt es immer mindestens 2, die die selbe Anzahl von Personen kennen. ### Beweis Wir wollen das Schubfachprinzip nutzen. Für die Personen $P = \{1, ... n\}$ betrachte die Abbildung $f: P \to \{0, ... n-1\}$, die jeder dieser Personen die Anzahl der Personen, die sie kennt, zuweist. Problem: $\vert P \vert = n = \vert \{1, ... n\} \vert$ Betrachte 2 Fälle: 1. Es gibt eine Person, die niemanden kennt, das heißt $\exists i \in P$ so dass $f(i) = 0$. Dann gilt $\forall j \in P \neq n - 1$ da "kennen" symmetrisch ist. Damit ist $f(P) \subseteq \{0, ... n-2\}$ und das Schubfachprinzip ist anwendbar. 2. Es gibt keine Person, die niemanden kennt, dann $f(P) \subseteq \{1, ... n-1\}$ und auch hier ist das Schubfachprinzip anwendbar. $$ \Box $$ **Beispiel 2**: In Bochum wohnen ca $350000$ Menschen, jeder Mensch hat zwischen $0$ und $150000$ Kopfhaare. $\Rightarrow$ es gibt mindestens 2 Menschen in Bochum mit der gleichen Anzahl Haare.