Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 14/latex
\setcounter{section}{14}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller36.jpg} }
\end{center}
\bildtext {Auch mit dem Ball spielt sie gern.} }
\bildlizenz { Waeller36.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
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.
\zwischenueberschrift{Partitionen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Set_partitions_5;_circles.svg} }
\end{center}
\bildtext {Die $52$ Partitionen einer fünfelementigen Menge.} }
\bildlizenz { Set_partitions_5;_circles.svg } {} {Watchduck} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Es sei $M$ eine Menge. Eine Teilmenge
\mavergleichskette
{\vergleichskette
{ P
}
{ \subseteq }{ \mathfrak {P} \, (M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {Partition}{}
von $M$, falls die folgenden Bedingungen erfüllt sind.
\aufzaehlungdrei{Für alle
\mavergleichskette
{\vergleichskette
{A
}
{ \in }{P
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskette
{\vergleichskette
{A
}
{ \neq }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für
\mavergleichskette
{\vergleichskette
{A,B
}
{ \in }{ P
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{A
}
{ \neq }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
gilt
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} { \biguplus_{A \in P} A
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine disjunkte Vereinigung von nichtleeren Teilmengen, die auch die \stichwort {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
\zusatzklammer {die \stichwort {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.
\inputbemerkung
{}
{
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.
}
\inputfaktbeweis
{Menge/Äquivalenzrelation/Partition/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $M$ eine Menge.}
\faktfolgerung {Es gibt eine natürliche Korrespondenz zwischen
\definitionsverweis {Äquivalenzrelationen}{}{}
auf $M$ und
\definitionsverweis {Partitionen}{}{}
auf $M$.}
\faktzusatz {Dabei wird einer Äquivalenzrelation die Menge ihrer
\definitionsverweis {Ä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.}
\faktzusatz {}
}
{
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.
\inputbemerkung
{}
{
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
\mathl{f^{-1} (j)}{} zu
\mavergleichskette
{\vergleichskette
{j
}
{ \in }{\{1 , \ldots , k\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Partition der Ausgangsmenge. Es liegt also eine natürliche Abbildung
\maabbeledisp {\Psi} { \operatorname{Surj}(n,k)} { \operatorname{Part}(n,k)
} {f} { \{ f^{-1}(j), j \in \{ 1 , \ldots , k \} \}
} {,}
vor
\zusatzklammer {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
\definitionsverweis {Äquivalenzrelation}{}{,}
bei der man
\mavergleichskette
{\vergleichskette
{f
}
{ \sim }{g
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
dadurch festlegt, dass es eine
\definitionsverweis {Permutation}{}{}
$h$ auf $\{ 1 , \ldots , k \}$ mit
\mavergleichskettedisp
{\vergleichskette
{f
}
{ =} {h \circ g
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt
\zusatzklammer {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
\mathl{\operatorname{Part}(n,k)}{} als
\definitionsverweis {Quotientenmenge}{}{}
zu dieser Äquivalenzrelation ansehen.
}
\zwischenueberschrift{Stirling-Zahlen zweiter Art}
\inputdefinition
{}
{
Die Anzahl der
\definitionsverweis {Partitionen}{}{}
einer $n$-elementigen Menge $M$ in $k$ Blöcke heißt
\definitionswort {Stirling-Zahl zweiter Art}{.}
Sie wird mit
\mathl{S ( { n } , { k } )}{} bezeichnet.
}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \{a,b,c\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine dreielementige Menge. Es ist
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ S ( { 3 } , { 2 } )
}
{ =} { 3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Set partitions 4; Hasse; circles.svg} }
\end{center}
\bildtext {Alle Partitionen einer vierelementigen Menge, geordnet nach Partitionsverfeinerung.} }
\bildlizenz { Set partitions 4; Hasse; circles.svg } {} {Watchduck} {CC-by-sa 3.0} {} {}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \{a,b,c,d\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine vierelementige Menge. Es ist
\mavergleichskettedisp
{\vergleichskette
{ 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
\mathdisp {\{ \{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
\mathdisp {\{\{a,b\},\{c,d\}\},\ \{\{a,c\},\{b,d\}\},\ \{\{a,d\},\{b,c\}\}} { , }
also ist isgesamt
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ 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.
\inputfaktbeweis
{Stirling-Zahl/2. Art/Partition/Extremwerte/Fakt}
{Lemma}
{}
{
\faktsituation {Für die
\definitionsverweis {Stirling-Zahlen zweiter Art}{}{}}
\faktuebergang {gelten die folgenden Formeln
\zusatzklammer {es sei
\mavergleichskettek
{\vergleichskettek
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}}
\faktfolgerung {\aufzaehlungvier{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { 1 } )
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { 2 } )
}
{ =} { 2^{n-1} -1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { n-1 } )
}
{ =} { \binom { n } { 2 }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { n } )
}
{ =} { 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
(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.
\inputfaktbeweis
{Stirling-Zahl/2. Art/Äquivalenzrelation/Fakt}
{Lemma}
{}
{
\faktsituation {Die Anzahl der
\definitionsverweis {Äquivalenzrelationen}{}{}
auf einer $n$-elementigen Menge mit $k$
\definitionsverweis {Äquivalenzklassen}{}{}}
\faktfolgerung {ist $S ( { n } , { k } )$.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies ist klar aufgrund von Lemma 14.3.
\inputfaktbeweis
{Endliche Mengen/Kugel und Urnen/Stirling-Zahl/2. Art/Fakt}
{Lemma}
{}
{
\faktsituation {Die
\definitionsverweis {Stirlingsche Zahl zweiter Art}{}{}
\mathl{S ( { n } , { k } )}{}}
\faktfolgerung {beschreibt die Anzahl an Möglichkeiten, $n$ unterscheidbare Kugeln auf $k$ ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.}
\faktzusatz {}
\faktzusatz {}
}
{
Das ist klar.
\inputfaktbeweis
{Endliche Mengen/Surjektive Abbildungen/Stirling-Zahl/2. Art/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
von $A$ nach $B$ gleich
\mathl{k! S ( { n } , { k } )}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Zu einer Abbildung
\maabb {f} {A} {B
} {}
gehört die Faserzerlegung
\mathbed {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.
\zwischenueberschrift{Rekursionseigenschaften}
Zur Berechnung der Anzahl von Partitionen ist die folgende Rekursionsformel in der Regel besser als die folgenden expliziten Formeln.
\inputfaktbeweis
{Partitionen/Stirling-Zahlen zweiter Art/Rekursion/Fakt}
{Lemma}
{}
{
\faktsituation {Die
\definitionsverweis {Stirling-Zahlen zweiter Art}{}{}
erfüllen die Rekursionsformel}
\faktfolgerung {
\mavergleichskettedisp
{\vergleichskette
{ S ( { n+1 } , { k } )
}
{ =} {k \cdot S ( { n } , { k } ) + S ( { n } , { k-1 } )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $M$ eine $(n+1)$-elementige Menge,
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element und
\mavergleichskettedisp
{\vergleichskette
{N
}
{ \defeq} {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
\mathl{B_1 , \ldots , B_k}{} die Blöcke sind, so ist
\mathl{B_1 \cap N , \ldots , B_k \cap N}{} eine Partition von $N$ mit $k$ Blöcken. Deren Anzahl beträgt
\mathl{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.
Mit dieser Rekursionsformel kann man direkt eine Tabelle für die Stirling-Zahlen zweiter Art erstellen.
\mathdisp {\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}} { }
\inputfaktbeweis
{Partitionen/Stirling-Zahlen zweiter Art/Summendarstellungen/Fakt}
{Satz}
{}
{
\faktsituation {Für die
\definitionsverweis {Stirling-Zahlen zweiter Art}{}{}
gelten die folgenden Beschreibungen.}
\faktfolgerung {\aufzaehlungvier{
\mavergleichskettedisp
{\vergleichskette
{ 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 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { k } )
}
{ =} { \sum_{c_1+c_2 + \cdots + c_k = n-k} 1^{c_1} 2^{c_2} \cdots k^{c_k}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ 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}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{
\mavergleichskettedisp
{\vergleichskette
{ S ( { n } , { k } )
}
{ =} { { \frac{ 1 }{ k! } } \sum_{j = 0}^{k} (-1)^{k-j} \binom { k } { j } j^{ n}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir verwenden durchgehend
Lemma 14.11,
das besagt, dass
\mathl{k! S ( { n } , { k } )}{} gleich der Anzahl der surjektiven Abbildungen einer $n$-elementigen Menge in eine $k$-elementige Menge ist.
\aufzaehlungvier{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
\mathdisp {\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
\mavergleichskette
{\vergleichskette
{c_j
}
{ = }{a_j -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ersetzt, so erhält man die Behauptung.
}{Dies ergibt sich aus Teil (2). Zu einem Tupel
\mathl{(i_1 , \ldots , i_{n-k})}{} der Indexmenge aus Teil (3) definiert man
\mavergleichskettedisp
{\vergleichskette
{c_j
}
{ \defeq} { { \# \left( { \left\{ s \mid i_s = j \right\} } \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{j
}
{ = }{ 1 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Umgekehrt definiert man zu einem Tupel
\mathl{(c_1 , \ldots , c_{k})}{} der Indexmenge aus Teil (2) die Zahlen
\mavergleichskettedisp
{\vergleichskette
{i_t
}
{ =} { j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für $t$ zwischen ausschließlich
\mathkor {} {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.
}
\zwischenueberschrift{Die Bellzahl}
\inputdefinition
{}
{
Die Anzahl der \definitionsverweis {Partitionen}{}{} einer $n$-elementigen Menge heißt \definitionswort {Bellzahl}{} und wird mit $B_n$ bezeichnet.
}
{Partitionen/Bellzahl/Einfache Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Die
\definitionsverweis {Bellzahlen}{}{}}
\faktuebergang {erfüllen die folgenden Gesetzmäßigkeiten.}
\faktfolgerung {\aufzaehlungzwei {
\mavergleichskettedisp
{\vergleichskette
{B_n
}
{ =} { \sum_{k = 1}^n S ( { n } , { k } )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
} {
\mavergleichskettedisp
{\vergleichskette
{B_{n+1}
}
{ =} { \sum_{i = 0}^n \binom { n } { i } B_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 14.10. }