Endliche Menge/Partitionen/Interpretationen/Einführung/Textabschnitt

Die ${}52$ Partitionen einer fünfelementigen Menge.

Definition

Es sei ${}M$ eine Menge. Eine Teilmenge ${}P\subseteq {\mathfrak {P}}\,(M)$ heißt Partition von ${}M$, falls die folgenden Bedingungen erfüllt sind.

1. Für alle ${}A\in P$ gilt ${}A\neq \emptyset$.
2. Für ${}A,B\in P$, ${}A\neq B$, gilt ${}A\cap B=\emptyset$.
3. Die Elemente von ${}P$ bilden eine Überdeckung von ${}M$, d.h. jedes Element von ${}M$ liegt in mindestens einem Element von ${}P$.

Es ist also

${}M=\biguplus _{A\in P}A\,$

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 ${}n$ Elementen in ${}k$ 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 ${}m$ Personen in ${}k$ 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 ${}M$ eine Menge.

Es gibt eine natürliche Korrespondenz zwischen Äquivalenzrelationen auf ${}M$ und Partitionen auf ${}M$.

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 Fakt  (2) begründet. Die Rückrichtung ist klar, man kann auch Fakt heranziehen. Dass die Zuordnungen invers zueinander sind, ist auch klar.

$\Box$

Bemerkung  

Partitionen stehen in einem engen Verhältnis zu surjektiven Abbildungen. Eine surjektive Abbildung ${}f$ von einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge liefert über die Menge der Fasern ${}f^{-1}(j)$ zu ${}j\in \{1,\ldots ,k\}$ eine Partition der Ausgangsmenge. Es liegt also eine natürliche Abbildung

$\Psi \colon \operatorname {Surj} (n,k)\longrightarrow \operatorname {Part} (n,k),\,f\longmapsto \{f^{-1}(j),j\in \{1,\ldots ,k\}\},$

vor (mit naheliegenden Bezeichnungen). Diese ist surjektiv, da man bei einer Partition in ${}k$ Blöcke die Blöcke mit ${}1$ bis ${}k$ durchnummerieren kann und dann die Abbildung heranziehen kann, die jedes Element auf die Nummer ihres Blockes abbildet. Die Abbildung ${}\Psi$ kann man auch folgendermaßen interpretieren: Man definiert auf der Menge der surjektiven Abbildungen eine Äquivalenzrelation, bei der man ${}f\sim g$ dadurch festlegt, dass es eine Permutation ${}h$ auf ${}\{1,\ldots ,k\}$ mit

${}f=h\circ g\,$

gibt (siehe Aufgabe). Dabei sind zwei surjektive Abbildungen genau dann zueinander äquivalent, wenn sie die gleiche Partition definieren. Aufgrund von Fakt kann man also ${}\operatorname {Part} (n,k)$ als Quotientenmenge zu dieser Äquivalenzrelation ansehen.