Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 14/kontrolle
In dieser Vorlesung besprechen wir Partitionen einer Menge in Beziehung zu Äquivalenzrelationen und insbesondere die Anzahl von Partitionen einer -elementigen Menge in Blöcke. Diese Zahl hängt eng mit der Anzahl von surjektiven Abbildungen zusammen.
- Partitionen
Es sei eine Menge. Eine Teilmenge heißt Partition von , falls die folgenden Bedingungen erfüllt sind.
- Für alle gilt .
- Für , , gilt .
- Die Elemente von bilden eine Überdeckung von , d.h. jedes Element von liegt in mindestens einem Element von .
Es ist also
eine disjunkte Vereinigung von nichtleeren Teilmengen, die auch die Blöcke der Partition heißen. Da eine Partition als Teilmenge der Potenzmenge angesetzt wird, sind zwei Partitionen genau dann gleich, wenn sie die gleichen Blöcke enthalten. Die Blöcke sind nicht geordnet oder nummeriert. Als Extremfälle gibt es die Partition in einen einzigen Block, der alle Elemente enthält (die Klumpenpartition) und die Partition, bei der jeder Block einelementig ist. Wir werden hier Partitionen von endlichen Mengen in den Mittelpunkt stellen. Typischerweise werden wir eine Mengen mit Elementen in Blöcke aufteilen. Jeder Block hat dann eine gewisse Anzahl, und man kann diese Situation kombinatorisch studieren. Dabei ist eine Partition stets von ihrem numerischen Typ zu unterscheiden. Wenn beispielsweise eine fünfelementige Menge in zwei Blöcke mit zwei bzw. drei Elementen eingeteilt wird, so stehen dahinter zehn verschiedene Partitionen. Es ist aber sinnvoll, sich alle Partitionen entlang solcher numerischer Überlegungen zu vergegenwärtigen.
Typische Interpretationen einer Partition treten in vielen Kontexten auf:
Man möchte eine Menge von Personen in Teams aufteilen. Jede Person soll in genau einem Team sein, es gibt keine leeren Teams und die Teams haben keine Benennung, sondern sie sind allein durch die zu ihnen gehörigen Personen bestimmt.
Man möchte unterscheidbare Kugeln auf ununterscheidbare Urnen verteilen, wobei keine Urne leer bleiben darf.
Man möchte aus einer Ansammlung von Blumen Blumensträuße binden.
Es sei eine Menge.
Es gibt eine natürliche Korrespondenz zwischen Äquivalenzrelationen auf und Partitionen auf .
Dabei wird einer Äquivalenzrelation die Menge ihrer Äquivalenzklassen zugeordnet, und einer Partition wird diejenige Äquivalenzrelation zugeordnet, bei der zwei Elemente als äquivalent angesehen werden, wenn sie in dem gleichen Block der Partition liegen.
Dass eine Äquivalenzrelation eine Partition festlegt, wurde in Lemma 11.12 (2) begründet. Die Rückrichtung ist klar, man kann auch Lemma 10.10 heranziehen. Dass die Zuordnungen invers zueinander sind, ist auch klar.
Partitionen stehen in einem engen Verhältnis zu surjektiven Abbildungen. Eine surjektive Abbildung von einer -elementigen Menge in eine -elementige Menge liefert über die Menge der Fasern zu eine Partition der Ausgangsmenge. Es liegt also eine natürliche Abbildung
vor (mit naheliegenden Bezeichnungen). Diese ist surjektiv, da man bei einer Partition in Blöcke die Blöcke mit bis durchnummerieren kann und dann die Abbildung heranziehen kann, die jedes Element auf die Nummer ihres Blockes abbildet. Die Abbildung kann man auch folgendermaßen interpretieren: Man definiert auf der Menge der surjektiven Abbildungen eine Äquivalenzrelation, bei der man dadurch festlegt, dass es eine Permutation auf mit
gibt (siehe Aufgabe 14.15). Dabei sind zwei surjektive Abbildungen genau dann zueinander äquivalent, wenn sie die gleiche Partition definieren. Aufgrund von Lemma 11.13 kann man also als Quotientenmenge zu dieser Äquivalenzrelation ansehen.
- Stirling-Zahlen zweiter Art
Die Anzahl der Partitionen einer -elementigen Menge in Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit bezeichnet.
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
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.
Für die Stirling-Zahlen zweiter Art gelten die folgenden Formeln (es sei ).
(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 Satz 2.11.
Die Anzahl der Äquivalenzrelationen auf einer -elementigen Menge mit Äquivalenzklassen
ist .
Dies ist klar aufgrund von Lemma 14.3.
Die Stirlingsche Zahl zweiter Art
beschreibt die Anzahl an Möglichkeiten, unterscheidbare Kugeln auf ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.
Das ist klar.
Es sei eine -elementige Menge und eine -elementige Menge.
Dann ist die Anzahl der surjektiven Abbildungen von nach gleich .
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.
- Rekursionseigenschaften
Zur Berechnung der Anzahl von Partitionen ist die folgende Rekursionsformel in der Regel besser als die folgenden expliziten Formeln.
Die Stirling-Zahlen zweiter Art erfüllen die Rekursionsformel
Es sei eine -elementige Menge, ein fixiertes Element und
Wir teilen die Partitionen von auf je nachdem, ob ein Block in der Partition ist oder nicht. Eine Partition von , bei der einen Einzelblock bildet, entspricht einer Partition von in Blöcke, was den zweiten Summanden erklärt. Bei einer Partition von , bei der keinen Einzelblock bildet, gehört zu einem Block mit zumindest zwei Elementen. Wenn die Blöcke sind, so ist eine Partition von mit Blöcken. Deren Anzahl beträgt . Eine jede solche Partition kann man auf verschiedene Weisen zu einer Partition auf fortsetzen, je nachdem, zu welchem Block man hinzuschlägt. Dies ergibt den ersten Summanden.
Mit dieser Rekursionsformel kann man direkt eine Tabelle für die Stirling-Zahlen zweiter Art erstellen.
Für die Stirling-Zahlen zweiter Art gelten die folgenden Beschreibungen.
Wir verwenden durchgehend Lemma 14.11, das besagt, dass gleich der Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge ist.
- Dies folgt aus Lemma 13.5.
- Nach
Satz 13.6
ist die Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge gleich
Wenn man diesen Ausdruck durch dividiert, und überall ersetzt, so erhält man die Behauptung.
- Dies ergibt sich aus Teil (2). Zu einem Tupel der Indexmenge aus Teil (3) definiert man
für . Umgekehrt definiert man zu einem Tupel der Indexmenge aus Teil (2) die Zahlen
für zwischen ausschließlich und einschließlich . Diese Zuordnungen sind invers zueinander und die aufzusummierenden Produkte stimmen überein.
- Dies folgt aus Satz 13.7.
- Die Bellzahl
Die Anzahl der Partitionen einer -elementigen Menge heißt Bellzahl und wird mit bezeichnet.
