265 lines
7.1 KiB
Markdown
265 lines
7.1 KiB
Markdown
|
---
|
||
|
|
title: Wichtige kombinatorische Probleme
|
||
|
|
date: 2018-10-17
|
||
|
|
---
|
||
|
|
|
||
|
|
Ein Ziel: Anzahl der Möglichkeiten, $n$ Bälle auf $m$ Urnen zu verteilen, zu verstehen.
|
||
|
|
|
||
|
|
**Vorher**:
|
||
|
|
|
||
|
|
1. Mengenpartitionen
|
||
|
|
2. Permutationen
|
||
|
|
3. Zahlpartitionen (geordnet und ungeordnet)
|
||
|
|
|
||
|
|
In vielen Fällen erhalten wir "nur" eine Rekursionsformel und keine geschlossene Formel, um die Anzahl zu bestimmen
|
||
|
|
(siehe auch Binomialkoeffizient).
|
||
|
|
|
||
|
|
|
||
|
|
# Mengenpartitionen
|
||
|
|
|
||
|
|
Endliche Menge $A$, $k \in \mathbb{N}$
|
||
|
|
|
||
|
|
> Bild
|
||
|
|
|
||
|
|
Wir wollen $A$ unterteilen in $k$ nicht-leere Teilmengen $A_i$, $i \in \{ 1,...k \}$, so dass $A_i \neq \emptyset$,
|
||
|
|
$A_i \cap A_j = \emptyset$, $i \neq j$, also paarweise disjunkt und
|
||
|
|
$\bigcup\limits_{i=1}^n A_i = \dot{\bigcup}_{i=1}^n A_i = A$.
|
||
|
|
|
||
|
|
## **Definition**: Sterling-Zahl zweiter Art
|
||
|
|
|
||
|
|
Eine $k$-Partition einer endlichen Menge $A$ ist eine ungeordnete Partition von $A$ in $k$ nicht-leere Teilmengen
|
||
|
|
$A_i$, $i \in \{1,...k\}$. Die Anzahl dieser $k$-Partitionen bezeichnen wir mit $S_{n,k}$ und heißt
|
||
|
|
**Sterling-Zahl zweiter Art**.
|
||
|
|
|
||
|
|
## **Satz**: Sterling-Zahl zweiter Art
|
||
|
|
|
||
|
|
Für alle $n \geq k$ gilt $S_{n,k} = S_{n-1,k-1} + k \cdot S_{n-1,k}$.
|
||
|
|
|
||
|
|
## **Beweis**: Sterling-Zahl zweiter Art
|
||
|
|
|
||
|
|
Wir teilen die Anzahl der $k$-Partitionen der Menge $A = \{1,...n\}$ auf in zwei disjunkte Fälle.
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
|
||
|
|
$\{n\}$ ist eine der $k$ Teilmengen. Damit bilden die weiteren Teilmengen eine $(k-1)$-Partition der Menge
|
||
|
|
$A \setminus \{n\} = A' = \{1,...n-1\}$. Dafür gibt es $S_{n-1,k-1}$ Möglichkeiten.
|
||
|
|
|
||
|
|
2. Fall:
|
||
|
|
|
||
|
|
$\{n\}$ ist keine der $k$ Teilmengen. Wir betrachten die $k$-Partition von $A' = \{1,...n-1\}$. Davon gibt es
|
||
|
|
$S_{n-1,k}$ viele. Wir erhalten aus jeder dieser Partitionen eine Partition von $A = A' \cup \{n\}$ indem wir $n$ in
|
||
|
|
eine der $k$ Teilmengen hinzufügen. Damit erhalten wir in diesem Fall $k \cdot S_{n-1,k}$ Möglichkeiten.
|
||
|
|
|
||
|
|
Summenformel liefert
|
||
|
|
$$
|
||
|
|
S_{n,k} = S_{n-1,k-1} + k \cdot S_{n-1,k}
|
||
|
|
$$
|
||
|
|
$$
|
||
|
|
\tag*{$\Box$}
|
||
|
|
$$
|
||
|
|
|
||
|
|
**Beispiel**: $n = 4$, $k = 3$, $A = \{1,2,3,4\}$
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
* $\{1,2\} \cup \{3\} \cup \{4\}$
|
||
|
|
* $\{1,3\} \cup \{2\} \cup \{4\}$
|
||
|
|
* $\{2,3\} \cup \{1\} \cup \{4\}$
|
||
|
|
|
||
|
|
2. Fall: 3-Partition von $A' = \{1,2,3\}$ ist $\{1\} \cap \{2\} \cap \{3\}$ und damit
|
||
|
|
* $\{1,4\} \cap \{2\} \cap \{3\}$
|
||
|
|
* $\{1\} \cap \{2,4\} \cap \{3\}$
|
||
|
|
* $\{1\} \cap \{2\} \cap \{3,4\}$
|
||
|
|
|
||
|
|
$$
|
||
|
|
\Rightarrow S_{4,3} = 3 + 3 \cdot 1 = 6
|
||
|
|
$$
|
||
|
|
|
||
|
|
# Permutationen
|
||
|
|
|
||
|
|
Eine Permutation auf $\{1,...n\}$ ist eine bijektive Abbildung $\pi : \{1,...n\} \to \{1,...n\}$.
|
||
|
|
|
||
|
|
1. Wir wissen schon, dass es insgesamt $n!$ solcher Permutationen gibt
|
||
|
|
2. Wir wissen, wie viele Permutationen es gibt, die keinen Fixpunkt haben
|
||
|
|
|
||
|
|
Mögliche Darstellungen von $\pi$:
|
||
|
|
|
||
|
|
1. als Tabelle
|
||
|
|
|
||
|
|
$$
|
||
|
|
\pi : \{1,...n\} \to \{1,...n\}
|
||
|
|
$$
|
||
|
|
|
||
|
|
| i | 1 | 2 | ... | n |
|
||
|
|
| :---: | :---: | :---: | :---: | :---: |
|
||
|
|
| $\pi(i)$ | $\pi(1)$ | $\pi(2)$ | | $\pi(n)$ |
|
||
|
|
|
||
|
|
**Beispiel**: $n = 5$
|
||
|
|
|
||
|
|
| i | 1 | 2 | 3 | 4 | 5 |
|
||
|
|
| :---: | :---: | :---: | :---: | :---: | :---: |
|
||
|
|
| $\pi(i)$ | 3 | 4 | 1 | 2 | 5 |
|
||
|
|
|
||
|
|
2. als Produkt von Zykeln
|
||
|
|
|
||
|
|
Ein Zykel der Länge $l$ ist $(i_1,i_2,...i_l)$ und entspricht der Permutation $\pi : \{1,...n\} \to \{1,...n\}$ mit
|
||
|
|
$\pi(i_1) = i_2$, $\pi(i_2) = i_3$, $\pi(i_{l-1}) = i_l$ und $\pi(i_l) = i_i$. Für $x \notin \{i_1,...i_l\}$ mit
|
||
|
|
$x \in \{1,...n\}$ gilt $\pi(x) = x$.
|
||
|
|
|
||
|
|
**Beispiel**: $n = 5$
|
||
|
|
|
||
|
|
Der Zykel $(3 2 4 1)$ entspricht der Permutation
|
||
|
|
|
||
|
|
| i | 1 | 2 | 3 | 4 | 5 |
|
||
|
|
| :---: | :---: | :---: | :---: | :---: | :---: |
|
||
|
|
| $\pi(i)$ | 3 | 4 | 2 | 1 | 5 |
|
||
|
|
|
||
|
|
Ein Produkt von Zykeln entspricht der Hintereinanderführung der einzelnen Permutationen (gelesen von rechts nach links).
|
||
|
|
|
||
|
|
**Beispiel**: $n = 5$
|
||
|
|
|
||
|
|
$$
|
||
|
|
(3 2 4) (5 1 2) \\
|
||
|
|
\pi_2 \text{ } \pi_1
|
||
|
|
$$
|
||
|
|
|
||
|
|
Entspricht $\pi = \pi_2 \circ \pi_1$ also
|
||
|
|
|
||
|
|
| i | 1 | 2 | 3 | 4 | 5 |
|
||
|
|
| :---: | :---: | :---: | :---: | :---: | :---: |
|
||
|
|
| $\pi_1(i)$ | 2 | 5 | 3 | 4 | 1 |
|
||
|
|
| $\pi_2(i)$ | 1 | 4 | 2 | 3 | 5 |
|
||
|
|
|
||
|
|
Damit $\pi = \pi_2 \circ \pi_1$ gegeben als
|
||
|
|
|
||
|
|
| i | 1 | 2 | 3 | 4 | 5 |
|
||
|
|
| :---: | :---: | :---: | :---: | :---: | :---: |
|
||
|
|
| $\pi(i)$ | 4 | 5 | 2 | 3 | 1 |
|
||
|
|
|
||
|
|
Insbesondere interessant sind Produkte von Zykeln die disjunkte Elemente haben.
|
||
|
|
|
||
|
|
Insbesondere gilt:
|
||
|
|
|
||
|
|
## **Satz**: Permutation als Produkt von Zykeln
|
||
|
|
|
||
|
|
Jede Permutation lässt sich als Produkt con elementfremden Zyklen schreiben.
|
||
|
|
|
||
|
|
## **Beweis**: Permutation als Produkt von Zykeln
|
||
|
|
|
||
|
|
Gegeben: $\pi : \{1,...n\} \to \{1,...n\}$.
|
||
|
|
|
||
|
|
Wir konstruieren eine solche Darstellung. Wir starten mit einem Element (z.B. 1) und betrachten die Sequenz
|
||
|
|
|
||
|
|
$$
|
||
|
|
i_1 = 1 \\
|
||
|
|
i_2 = \pi(i_1) = \pi(1) \\
|
||
|
|
i_3 = \pi(i_2) = \pi(\pi(i1)) \\
|
||
|
|
\text{usw.}
|
||
|
|
$$
|
||
|
|
|
||
|
|
Da die Menge $\{1,...n\}$ endlich ist, gibt es ein minimales $l$, so dass $i_{l+1} = \pi(i_i) = i_1$. Damit erhalten wir
|
||
|
|
den Zykel $(i_1,i_2,...i_l)$. Wir starten den Prozess erneut mit einem Element aus $\{1,...n\} \setminus \{i_1,...i_l\}$
|
||
|
|
bis alle Elemente aus $\{1,...n\}$ in einem Zykel enthalten sind.
|
||
|
|
|
||
|
|
$$
|
||
|
|
\tag*{$\Box$}
|
||
|
|
$$
|
||
|
|
|
||
|
|
**Beispiel**: Permutation (1)
|
||
|
|
|
||
|
|
$$
|
||
|
|
\pi = \pi_2 \circ \pi_1 \\
|
||
|
|
(1,4,3,2,5) \\
|
||
|
|
\pi(1) = 4 \\
|
||
|
|
\pi(4) = 3 \\
|
||
|
|
\pi(3) = 2 \\
|
||
|
|
\pi(2) = 5 \\
|
||
|
|
\pi(5) = \underline{1} \\
|
||
|
|
$$
|
||
|
|
|
||
|
|
**Beispiel**: Permutation (2)
|
||
|
|
|
||
|
|
$$
|
||
|
|
(1,3)(2,4)(5) \\
|
||
|
|
\pi(1) = 3, \pi(3) = \underline{1} \\
|
||
|
|
\pi(2) = 4, \pi(4) = \underline{2} \\
|
||
|
|
\pi(5) = 5
|
||
|
|
$$
|
||
|
|
|
||
|
|
Diese Darstellung ist nicht eindeutig, denn
|
||
|
|
|
||
|
|
1. Wir können die Reihenfolge der Zyklen ändern.
|
||
|
|
|
||
|
|
Beispiel: $(1,3)(2,4)(5) = (2,4)(5)(1,3$
|
||
|
|
|
||
|
|
2. Wir können innerhalb eines Zykels rotieren
|
||
|
|
|
||
|
|
Beispiel: $(1,4,3,2,5) = (2,5,1,4,3)$
|
||
|
|
|
||
|
|
Bis auf diese Modifikationen ist diese Darstellung eindeutig.
|
||
|
|
|
||
|
|
## **Definition**: Sterling-Zahl erster Art
|
||
|
|
|
||
|
|
Die Anzahl der Permutationen auf $\{1,...n\}$ die in genau $k$ Zyklen zerfallen (wobei wir Fixpunkte, d.h. Zyklen der
|
||
|
|
Länge 1 mitzählen) bezeichnen wir mit $s_{n,k}$ und heißt *Sterling-Zahl erster Art*.
|
||
|
|
|
||
|
|
Auch dafür gibt es eine Rekursionsformel.
|
||
|
|
|
||
|
|
## **Satz**: Sterling-Zahl erster Art
|
||
|
|
|
||
|
|
Für $n \ge k$ gilt $s_{n,k} = s_{n-1,k-1} + (n-1) \cdot s_{n-1,k}$
|
||
|
|
|
||
|
|
## **Beweis**: Sterling-Zahl erster Art
|
||
|
|
|
||
|
|
Wir betrachten (wieder) zwei disjunkte Fälle von Permutationen auf $\{1,...n\}$, die in $k$ Zykeln zerfallen
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
Die Permutation hat $(n)$ als Zykel. Damit bilden die restlichen $(k-1)$ Zykeln eine Permutation der Elemente
|
||
|
|
$\{1,...n-1\}$. Davon gibt es $s_{n-1,k-1}$ viele.
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
Die Permutation hat $(n)$ *nicht* als Zykel. Wir betrachten hier eine Permutation auf $\{1,...n-1\}$, die in $k$
|
||
|
|
Zykeln zerfällt. Davon gibt es $s_{n-1,k}$ viele. Wir fügen das Element $n$ ein. Dafür gibt es $(n-1)$
|
||
|
|
Möglichkeiten. Damit gibt es im 2. Fall insgesamt $(n-1) \cdot s_{n-1,k}$ Möglichkeiten.
|
||
|
|
|
||
|
|
Summenformel liefert:
|
||
|
|
|
||
|
|
$$
|
||
|
|
s_{n,k} = s_{n-1,k-1} + (n-1) \cdot s_{n-1,k}
|
||
|
|
$$
|
||
|
|
$$
|
||
|
|
\tag*{$\Box$}
|
||
|
|
$$
|
||
|
|
|
||
|
|
**Beispiel**: $n = 4$ $\{1,2,3,4\}$
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
$$
|
||
|
|
2 = s_{3,1} = \begin{cases}
|
||
|
|
(1,2,3)(4) \\
|
||
|
|
(1,3,2)(4)
|
||
|
|
\end{cases}
|
||
|
|
$$
|
||
|
|
|
||
|
|
1. Fall:
|
||
|
|
$$
|
||
|
|
(1,2)(3) = \begin{cases}
|
||
|
|
(1,2,4)(3) \\
|
||
|
|
(1,4,2)(3) \\
|
||
|
|
(1,2)(3,4)
|
||
|
|
\end{cases} \\
|
||
|
|
(1,3)(2) = \begin{cases}
|
||
|
|
(1,3,4)(2) \\
|
||
|
|
(1,4,3)(2) \\
|
||
|
|
(1,3)(2,4)
|
||
|
|
\end{cases} \\
|
||
|
|
(2,3)(1) = \begin{cases}
|
||
|
|
(2,3,4)(1) \\
|
||
|
|
(2,4,3)(1) \\
|
||
|
|
(2,3)(1,4)
|
||
|
|
\end{cases}
|
||
|
|
$$
|
||
|
|
|
||
|
|
$$
|
||
|
|
s_{3,2} = 3
|
||
|
|
$$
|