notes/school/di-ma/20181009_2-kombinatorik.md

title	date
Kombinatorik	2018-10-09

Kombinatorik

Elementare Zählprobleme und Grundlegende Regeln

Beispiel

Gegeben

• 3 elementige Menge M = \{1, 2, 3\}

Frage

Wie viele Möglichkeiten gibt es, 2 Elemente azs M zu ziehen?

Antwort

It depends

---	geordnet	ungeordnet
mit zurücklegen	A: $(1,1),(1,2),(1,3)$ $(2,1),(2,2),(2,3)$ (3,1),(3,2),(3,3)	D: ${1,1},{1,2}{1,2}$ ${2,2},{3,2}$ \{3,3\}
ohne zurücklegen	B: $(1,2),(1,3)$ $(2,1),(2,3)$ (3,1),(3,2)	C: ${1,2},{1,3}$ ${2,3}$

Wie viele Möglichkeiten gibt es allgemein, aus einer $n$-elementingen Menge k elemente zu ziehen?

Zuerst: Einfache Grundregeln

Summenregel

Seien S, T endliche Mengen, disjunkt, d.h. S \cap T = \emptyset (Notation S \dot\cup T, disjunkte Vereinigung), dann gilt

| S \dot\cup T | = | S | + | T |

Allgemeiner: Gegeben S_1, S_2, ... S_n, endliche, disjunkte Mengen, dann gilt

| \dot\cup^n_{i=1} S_i | = | S_1 | + | S_2 | + ... + | S_n | = \sum\limits^n_{i=1} | S_i |

Produktregel

Seien S, T endliche Mengen, dann gilt

| S \times T | = | S | \cdot | T |

wobei

S \times T = \{(s,t) \mid s \in S, t \in T \}

Allgemeiner: Gegeben S_1, S_2, ... S_n endliche Mengen, dann gilt

\vert S_1 \times S_2 \times ... S_n \vert = \vert S_1 \vert \cdot \vert S_2 \vert \cdot ... \vert S_n \vert

Beispiel

S_1, ..., S_n = \{0, 1\}, n = 64 \\
\vert S^n \vert = \vert \{0,1\}^{64} \vert = 2^{64}

Anzahl der Zustände eines 64-bit Registers.

Gleichheitsregel

Seien S, T endliche Mengen und f: S \to T eine bijektive Abbildung, dann gilt

\vert S \vert = \vert T \vert

(eigentlich: Definition von "gleich groß")

Allgemeiner: Seien S, T endliche Mengen und f: S \to T eine k auf 1 Abbildung, d.h. \forall t \in T gilt \vert\{s \in S \mid f(s) = t \}\vert = \vert f^{-1}(t) \vert = k dann gilt

\vert S \vert = k \cdot \vert T \vert

Damit können wir nun die Fälle A - D untersuchen.

Fall A

In Fall A zählen wir $k$-Tupel mit Komponenten aus der $n$-elementigen Menge M, d.h. Elemente aus M \times M \times ... M = M^k

Aus der Produktregel folgt: Es gibt \vert M \vert^k = n^k Möglichkeiten

Satz

Die Anzahl der $k$-Tupel mit Komponenten aus einer $n$-elementigen Menge ist

n^k\\
\Box

Fall B

Wir ziehen aus einer $n$-elementigen Menge ohne zurücklegen

• Für die erste Komponente haben wir n Möglichkeiten
• Für die zweite Komponente haben wir n - 1 Möglichkeiten
• usw.

D.h. insgesamt haben wir n(n-1)(n-2)...(n-k+1) = n^{\underline{k}} Möglichkeiten ($k$-te absteigende Faktorielle).

Satz

Die Anzahl der $k$-Tupel mit paarweise verschiedenen Komponenten aus einer $n$-elementigen Menge ist

n^{\underline{k}} = n\cdot(n-1)\cdot...\cdot(n-k+1)

Wichtiger Spezialfall:

n = k

Dann ist das nichts anderes als die Anzahl der Permutationen von n Elementen

Beispiel

n = 3 \\
M = \{1,2,3\}

Mögliche Permutationen: (123), (132), (213), (231), (312), (321)

3! = 3\cdot2\cdot1 Möglichkeiten

n! = n\cdot(n-1)\cdot...\cdot2\cdot1 Möglichkeiten

Bemerkung: Es gilt

n^{\underline{k}} = \frac{n!}{(n-k)!}

Fall C

Wir zählen die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge.

Von fall B zu Fall c durch ignorieren der Reihenfolge.

Beachte die Abbildung die einem $k$-Tupel mit paarweise verschiedenen Komponenten (i_1, ..., i_k) die $k$-elementige Teilmenge \{i_1, ..., i_k\} zuordnet. Diese Abbildung ist k! - auf -1 da jede $k$-elementige Teilmenge auf $k!$ Arten angeordnet werden kann.

Damit folgt (Gleichheitsregel)

Satz

Die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge ist

\binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{n!}{k!(n-k)!}

\binom{n}{k} ist der Binomialkoeffizient.

Beispiel

n = 3, k = 2 \\
\binom{3}{2} = \frac{3!}{2! \cdot 1!} = \frac{3\cdot2}{2} = 3

Fall D

Hier zählen wir Multimengen. In einer Multimenge können Elemente mehrfach vorkommen, mit Vielfachheit.

In $k$-elementigen Multimengen addieren sich die Vielfachkeiten zu k.

Wir wollen die Gleichheitsregel anwenden. Dazu folgende Kodierung einer Multimenge:

• Zwei Symbole * und |
• Wir schreiben t Sterne * falls ein Element i Vielfachkeit t hat
• Übergang von i zu i-1 wird gekennzeichnet durch |

Beispiel 1

M = \{1,2,3,4,5\} und Multimenge S = \{1,1,1,3,3,4,4,4\} wird kodiert als

*** | | ** | *** |

Beispiel 2

T = \{1,1,5,5\} wird kodiert als

** | | | | **

Jede $k$-elementige Multimenge einer $n$-elementigen Menge entspricht eindeutig einer Sequenz aus k * Symbolen und n-1 | Symbolen.

Jede Sequenz von k * Symbolen und n-1 | Symbolen entspricht genau einer $k$-elementigen Multimenge.

Abbildung Multimenge \to Kodierungssequenz ist bijektiv.

Wegen der Gleichheitsregel können wir also genausogut die Anzahl der möglichen Kodierungssequenzen zählen.

Kodierungssequenz hat die Länge (n-1)+k und an k Stellen steht ein *. Dann gibt es genau $\binom{n-1+k}{k}$ solcher Sequenzen.

Satz

Die Anzahl der $k$-elementigen Multimengen einer $n$-elementigen Menge ist

\binom{n-1+k}{k}

Beispiel

25 Eissorten. Wie viele mögliche Eisbecher mit 5 Kugeln gibt es?

Antwort:

n = 25, k = 5 \\
\binom{25-1+5}{5} = \binom{29}{5} = 118755