Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 14

Auch mit dem Ball spielt sie gern.

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
Die Partitionen einer fünfelementigen Menge.

Definition  

Es sei eine Menge. Eine Teilmenge heißt Partition von , falls die folgenden Bedingungen erfüllt sind.

  1. Für alle gilt .
  2. Für , , gilt .
  3. 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.

Bemerkung  

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.




Lemma  

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.

Beweis  

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.


Bemerkung  

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

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 Satz 2.11.



Lemma  

Die Anzahl der Äquivalenzrelationen auf einer -elementigen Menge mit Äquivalenzklassen

ist .

Beweis  

Dies ist klar aufgrund von Lemma 14.3.



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.



Rekursionseigenschaften

Zur Berechnung der Anzahl von Partitionen ist die folgende Rekursionsformel in der Regel besser als die folgenden expliziten Formeln.


Lemma  

Die Stirling-Zahlen zweiter Art erfüllen die Rekursionsformel

Beweis  

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.



Satz  

Für die Stirling-Zahlen zweiter Art gelten die folgenden Beschreibungen.

Beweis  

Wir verwenden durchgehend Lemma 14.11, das besagt, dass gleich der Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge ist.

  1. Dies folgt aus Lemma 13.5.
  2. 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.

  3. 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.

  4. Dies folgt aus Satz 13.7.



Die Bellzahl

Definition  

Die Anzahl der Partitionen einer -elementigen Menge heißt Bellzahl und wird mit bezeichnet.



Lemma

Die Bellzahlen erfüllen die folgenden Gesetzmäßigkeiten.

Beweis

Siehe Aufgabe 14.10.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)