notes/school/di-ma/20181010_1-binomialkoeffizient.md

---
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.