Partitionen/Stirling-Zahlen zweiter Art/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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


Alle Partitionen einer vierelementigen Menge, geordnet nach Partitionsverfeinerung.


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.