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