# Partitionen/Stirling-Zahlen zweiter Art/Textabschnitt
## Definition

Die Anzahl der Partitionen einer $n$-elementigen Menge $M$ in $k$ Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit $S({n},{k})$ bezeichnet.

## Beispiel

Es sei $M=\{a,b,c\}$ eine dreielementige Menge. Es ist
    $S({3},{1})=S({3},{3})=1\,.$
Bei einer Partition dieser dreielementigen Menge in $2$ Blöcke besitzt ein Block ein Element und der andere Block dann zwei Elemente. Also ist
    $S({3},{2})=3\,.$

## Beispiel

Es sei $M=\{a,b,c,d\}$ eine vierelementige Menge. Es ist
    $S({4},{1})=S({4},{4})=1\,.$
Bei einer Partition dieser vierelementigen Menge in $2$ Blöcke gibt es von den Anzahlen her zwei Möglichkeiten: Der eine Block besitzt ein Element und der andere Block drei Elemente oder beide Blöcke besitzen zwei Elemente. Im ersten Fall gibt es $4$ Möglichkeiten, nämlich
    $\{\{a\},\{b,c,d\}\},\,\{\{b\},\{a,c,d\}\},\,\{\{c\},\{a,b,d\}\},\,\{\{d\},\{a,b,c\}\},$
im zweiten Fall gibt es $3$ Möglichkeiten, nämlich
    $\{\{a,b\},\{c,d\}\},\ \{\{a,c\},\{b,d\}\},\ \{\{a,d\},\{b,c\}\},$
also ist isgesamt
    $S({4},{2})=7\,.$
Bei einer Partition dieser vierelementigen Menge in $3$ Blöcke ist ein Block zweielementig und die beiden anderen sind einelementig. Davon gibt es so viele wie zweielementige Teilmengen, also
    $S({4},{3})=6\,.$
Wir formulieren einfache Regeln für die Stirlingschen Zahlen zweiter Art, wenn die Anzahl $k$ der Blöcke klein oder nahe bei $n$ ist.

## Lemma

Für die Stirling-Zahlen zweiter Art gelten die folgenden Formeln (es sei $n\geq 1$).

### Beweis

(1) und (4) sind klar. (2). Eine Partition in zwei Blöcke besteht aus einer nichtleeren Teilmenge mit einem nichtleeren Komplement, wobei es auf die Reihenfolge nicht ankommt. Da es in einer $n$-elementigen Menge $2^{n}$ Teilmengen gibt, gibt es $2^{n-1}$ Teilmengenpaare. Da das Teilmengenpaar, das die leere Menge enthält, keine Partition ist, muss man $1$ abziehen. (3). Bei einer Partition mit $n-1$ Blöcken sind $n-2$ Blöcke einelementig und ein Block ist zweielementig. Deshalb ist eine solche Partition dasselbe wie die Festlegung einer zweielementigen Teilmenge, und davon gibt es ${\binom {n}{2}}$ nach Fakt.
$\Box$

## Lemma

Die Anzahl der Äquivalenzrelationen auf einer $n$-elementigen Menge mit $k$ Äquivalenzklassen
ist $S({n},{k})$.

### Beweis

Dies ist klar aufgrund von Fakt.
$\Box$

## Lemma

Die Stirlingsche Zahl zweiter Art $S({n},{k})$
beschreibt die Anzahl an Möglichkeiten, $n$ unterscheidbare Kugeln auf $k$ ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.

### Beweis

Das ist klar.
$\Box$

## Lemma

Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge.
Dann ist die Anzahl der surjektiven Abbildungen von $A$ nach $B$ gleich $k!S({n},{k})$.

### Beweis

Zu einer Abbildung $f\colon A\rightarrow B$ gehört die Faserzerlegung $f^{-1}(b)$, $b\in B$, von $A$. Wenn die Abbildung surjektiv ist, so sind alle Fasern nicht leer und es liegt eine Partition von $A$ vor. Eine surjektive Abbildung liefert also eine Partition der Definitionsmenge und gleichzeitig eine Indizierung der Blöcke durch die Wertemenge. Dabei wird jede Partition genau $k!$ mal erreicht, da verschiedene Indizierungen die Partition nicht ändern.
$\Box$