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

In dieser Vorlesung besprechen wir Partitionen einer Menge in Beziehung zu Äquivalenzrelationen und insbesondere die Anzahl von Partitionen einer ${}n$ -elementigen Menge ${}M$ in ${}k$ Blöcke. Diese Zahl hängt eng mit der Anzahl von surjektiven Abbildungen zusammen.

Partitionen

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.

Für alle ${}A\in P$ gilt ${}A\neq \emptyset$ .
Für ${}A,B\in P$ , ${}A\neq B$ , gilt ${}A\cap B=\emptyset$ .
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 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.

\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 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 ${}\operatorname {Part} (n,k)$ als Quotientenmenge zu dieser Äquivalenzrelation ansehen.

Stirling-Zahlen zweiter Art

Definition

Die Anzahl der Partitionen einer ${}n$ -elementigen Menge ${}M$ in ${}k$ Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit ${}S({n},{k})$ bezeichnet.

Beispiel

Es sei ${}M=\{a,b,c\}$ eine dreielementige Menge. Es ist

{}S({3},{1})=S({3},{3})=1\,.

Bei einer Partition dieser dreielementigen Menge in ${}2$ Blöcke besitzt ein Block ein Element und der andere Block dann zwei Elemente. Also ist

{}S({3},{2})=3\,.

Beispiel

Es sei ${}M=\{a,b,c,d\}$ eine vierelementige Menge. Es ist

{}S({4},{1})=S({4},{4})=1\,.

Bei einer Partition dieser vierelementigen Menge in ${}2$ 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 ${}4$ Möglichkeiten, nämlich

\{\{a\},\{b,c,d\}\},\,\{\{b\},\{a,c,d\}\},\,\{\{c\},\{a,b,d\}\},\,\{\{d\},\{a,b,c\}\},

im zweiten Fall gibt es ${}3$ Möglichkeiten, nämlich

\{\{a,b\},\{c,d\}\},\ \{\{a,c\},\{b,d\}\},\ \{\{a,d\},\{b,c\}\},

also ist isgesamt

{}S({4},{2})=7\,.

Bei einer Partition dieser vierelementigen Menge in ${}3$ Blöcke ist ein Block zweielementig und die beiden anderen sind einelementig. Davon gibt es so viele wie zweielementige Teilmengen, also

{}S({4},{3})=6\,.

Wir formulieren einfache Regeln für die Stirlingschen Zahlen zweiter Art, wenn die Anzahl ${}k$ der Blöcke klein oder nahe bei ${}n$ ist.

Lemma

Für die Stirling-Zahlen zweiter Art gelten die folgenden Formeln (es sei ${}n\geq 1$ ).

${}S({n},{1})=1\,.$

${}S({n},{2})=2^{n-1}-1\,.$

${}S({n},{n-1})={\binom {n}{2}}\,.$

${}S({n},{n})=1\,.$

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 ${}n$ -elementigen Menge ${}2^{n}$ Teilmengen gibt, gibt es ${}2^{n-1}$ Teilmengenpaare. Da das Teilmengenpaar, das die leere Menge enthält, keine Partition ist, muss man ${}1$ abziehen. (3). Bei einer Partition mit ${}n-1$ Blöcken sind ${}n-2$ Blöcke einelementig und ein Block ist zweielementig. Deshalb ist eine solche Partition dasselbe wie die Festlegung einer zweielementigen Teilmenge, und davon gibt es ${}{\binom {n}{2}}$ nach Satz 2.11.

\Box

Lemma

Die Anzahl der Äquivalenzrelationen auf einer ${}n$ -elementigen Menge mit ${}k$ Äquivalenzklassen

ist ${}S({n},{k})$ .

Beweis

Dies ist klar aufgrund von Lemma 14.3.

\Box

Lemma

Die Stirlingsche Zahl zweiter Art ${}S({n},{k})$

beschreibt die Anzahl an Möglichkeiten, ${}n$ unterscheidbare Kugeln auf ${}k$ ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.

Beweis

Das ist klar.

\Box

Lemma

Es sei ${}A$ eine ${}n$ -elementige Menge und ${}B$ eine ${}k$ -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich ${}k!S({n},{k})$ .

Beweis

Zu einer Abbildung ${}f\colon A\rightarrow B$ gehört die Faserzerlegung ${}f^{-1}(b)$ , ${}b\in B$ , von ${}A$ . Wenn die Abbildung surjektiv ist, so sind alle Fasern nicht leer und es liegt eine Partition von ${}A$ 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 ${}k!$ mal erreicht, da verschiedene Indizierungen die Partition nicht ändern.

\Box

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

${}S({n+1},{k})=k\cdot S({n},{k})+S({n},{k-1})\,.$

Beweis

Es sei ${}M$ eine ${}(n+1)$ -elementige Menge, ${}m\in M$ ein fixiertes Element und

{}N:=M\setminus \{m\}\,.

Wir teilen die Partitionen von ${}M$ auf je nachdem, ob ${}\{m\}$ ein Block in der Partition ist oder nicht. Eine Partition von ${}M$ , bei der ${}\{m\}$ einen Einzelblock bildet, entspricht einer Partition von ${}N$ in ${}k-1$ Blöcke, was den zweiten Summanden erklärt. Bei einer Partition von ${}M$ , bei der ${}\{m\}$ keinen Einzelblock bildet, gehört ${}m$ zu einem Block mit zumindest zwei Elementen. Wenn ${}B_{1},\ldots ,B_{k}$ die Blöcke sind, so ist ${}B_{1}\cap N,\ldots ,B_{k}\cap N$ eine Partition von ${}N$ mit ${}k$ Blöcken. Deren Anzahl beträgt ${}S({n},{k})$ . Eine jede solche Partition kann man auf ${}k$ verschiedene Weisen zu einer Partition auf ${}M$ fortsetzen, je nachdem, zu welchem Block man ${}m$ hinzuschlägt. Dies ergibt den ersten Summanden.

\Box

Mit dieser Rekursionsformel kann man direkt eine Tabelle für die Stirling-Zahlen zweiter Art erstellen.

{\begin{array}{c}1\\1\quad 1\\1\quad 3\quad 1\\1\quad 7\quad 6\quad 1\\1\quad 15\quad 25\quad 10\quad 1\\1\quad 31\quad 90\quad 65\quad 15\quad 1\\1\quad 63\quad 301\quad 350\quad 140\quad 21\quad 1\\1\quad 127\quad 966\quad 1701\quad 1050\quad 266\quad 28\quad 1\\1\quad 255\quad 3025\quad 7770\quad 6951\quad 2646\quad 462\quad 36\quad 1\\\end{array}}

Satz

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

${}S({n},{k})={\frac {1}{k!}}\sum _{(r_{1},\ldots ,r_{k}):\,r_{1}+r_{2}+\cdots +r_{k}=n,\,r_{j}\geq 1}{\binom {n}{r_{1},\dotsc ,r_{k}}}\,.$

${}S({n},{k})=\sum _{c_{1}+c_{2}+\cdots +c_{k}=n-k}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}\,.$

${}S({n},{k})=\sum _{1\leq i_{1}\leq i_{2}\leq \ldots \leq i_{n-k}\leq k}i_{1}i_{2}\cdots i_{n-k}\,.$

${}S({n},{k})={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}\,.$

Beweis

Wir verwenden durchgehend Lemma 14.11, das besagt, dass ${}k!S({n},{k})$ gleich der Anzahl der surjektiven Abbildungen einer ${}n$ -elementigen Menge in eine ${}k$ -elementige Menge ist.

Dies folgt aus Lemma 13.5.
Nach Satz 13.6 ist die Anzahl der surjektiven Abbildungen einer ${}n$ -elementigen Menge in eine ${}k$ -elementige Menge gleich
$\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.$

Wenn man diesen Ausdruck durch ${}k!$ dividiert, und überall ${}c_{j}=a_{j}-1$ ersetzt, so erhält man die Behauptung.
Dies ergibt sich aus Teil (2). Zu einem Tupel ${}(i_{1},\ldots ,i_{n-k})$ der Indexmenge aus Teil (3) definiert man
${}c_{j}:={\#\left({\left\{s\mid i_{s}=j\right\}}\right)}\,$

für ${}j=1,\ldots ,k$ . Umgekehrt definiert man zu einem Tupel ${}(c_{1},\ldots ,c_{k})$ der Indexmenge aus Teil (2) die Zahlen

${}i_{t}=j\,$

für ${}t$ zwischen ausschließlich ${}c_{1}+\cdots +c_{j-1}$ und einschließlich ${}c_{1}+\cdots +c_{j-1}+c_{j}$ . Diese Zuordnungen sind invers zueinander und die aufzusummierenden Produkte stimmen überein.
Dies folgt aus Satz 13.7.