Partitionen/Stirling-Zahlen zweiter Art/Textabschnitt
Definition
Die Anzahl der Partitionen einer -elementigen Menge in Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit bezeichnet.
Beispiel
Es sei eine dreielementige Menge. Es ist
Bei einer Partition dieser dreielementigen Menge in Blöcke besitzt ein Block ein Element und der andere Block dann zwei Elemente. Also ist
Beispiel
Es sei eine vierelementige Menge. Es ist
Bei einer Partition dieser vierelementigen Menge in 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 Möglichkeiten, nämlich
im zweiten Fall gibt es Möglichkeiten, nämlich
also ist isgesamt
Bei einer Partition dieser vierelementigen Menge in Blöcke ist ein Block zweielementig und die beiden anderen sind einelementig. Davon gibt es so viele wie zweielementige Teilmengen, also
Wir formulieren einfache Regeln für die Stirlingschen Zahlen zweiter Art, wenn die Anzahl der Blöcke klein oder nahe bei ist.
Lemma
Für die Stirling-Zahlen zweiter Art gelten die folgenden Formeln (es sei ).
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 -elementigen Menge Teilmengen gibt, gibt es Teilmengenpaare. Da das Teilmengenpaar, das die leere Menge enthält, keine Partition ist, muss man abziehen. (3). Bei einer Partition mit Blöcken sind Blöcke einelementig und ein Block ist zweielementig. Deshalb ist eine solche Partition dasselbe wie die Festlegung einer zweielementigen Teilmenge, und davon gibt es nach Fakt.
Lemma
Die Anzahl der Äquivalenzrelationen auf einer -elementigen Menge mit Äquivalenzklassen
ist .
Beweis
Dies ist klar aufgrund von Fakt.
Lemma
Die Stirlingsche Zahl zweiter Art
beschreibt die Anzahl an Möglichkeiten, unterscheidbare Kugeln auf ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.
Beweis
Das ist klar.
Lemma
Es sei eine -elementige Menge und eine -elementige Menge.
Dann ist die Anzahl der surjektiven Abbildungen von nach gleich .
Beweis
Zu einer Abbildung gehört die Faserzerlegung , , von . Wenn die Abbildung surjektiv ist, so sind alle Fasern nicht leer und es liegt eine Partition von 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 mal erreicht, da verschiedene Indizierungen die Partition nicht ändern.
