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

title	date
Binomialkoeffizient	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.

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