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

Übungsaufgaben

Aufgabe

Zeige, dass die Anzahl der geordneten Partitionen mit eventuell leeren Blöcken zum Anzahltupel ${}r=(r_{1},\ldots ,r_{k})$ einer ${}n$-elementigen Menge gleich

${}{\binom {n}{r}}={\frac {n!}{r_{1}!\cdots r_{k}!}}\,$

ist.

Aufgabe

Bestimme die Stirlingzahlen zweiter Art ${}S({n},{k})$ für ${}n\leq 5$.

Aufgabe

Es sei ${}r\in \mathbb {N}$ fixiert. Zeige, dass die Stirling-Zahlen zweiter Art ${}S({n},{n-2})$ ein Polynom in ${}n$ vom Grad ${}4$ ist.

Kommentar:

Für die Stirling-Zahlen zweiter Art ${}S({n},{k})$ gilt generell, wenn ${}k$ nahe bei ${}n$ ist, wenn es also sehr viele Blöcke gibt, dass dann viele Blöcke einelementig sein müssen. Für diese gibt es dann keine Auswahl mehr. Man kann also diese Zahlen dadurch berechnen, dass man sich überlegt, welche Blockgrößen es überhaupt geben kann und wie viele Partitionen zu diesem Blocktyp gehören. Bei

${}k=n-2\,$

gibt es anzahlmäßig zwei Möglichkeiten: Es gibt einen Block mit drei Elementen, alle weiteren Blöcke sind einelementig, oder es gibt zwei Blöcke mit jeweils zwei Elementen, und wieder sind alle weiteren Blöcke einelementig. Für den ersten Fall gibt es

${}{\binom {n}{3}}={\frac {n(n-1)(n-2)}{6}}\,$

Möglichkeiten. Dies ist ein Polynom vom Grad ${}3$. Für den zweiten Fall muss man eine zweielementige Teilmenge aussuchen und dann aus den verbleibenden ${}n-2$ Elementen eine weitere zweielementige Teilmenge aussuchen, aber zusätzlich berücksichtigen, dass es auf die Reihenfolge der beiden zweielementigen Teilmengen nicht ankommt.

 

Aufgabe

Erstelle eine Formel für die Anzahl der „Pseudopartitionen“ einer ${}n$-elementigen Menge in ${}k$ Blöcke, wenn die Blöcke auch leer sein durfen, mit Hilfe der Stirlingzahlen zweiter Art.

Es sei ${}M$ eine Menge und ${}P$ und ${}Q$ seien Partitionen von ${}M$. Man sagt, dass ${}P$ feiner als ${}Q$ ist, wenn jeder Block von ${}P$ eine Teilmenge eines Blockes von ${}Q$ ist.

Aufgabe

Es sei ${}M=\{a,b,c,d\}$ und es sei ${}V$ die Menge der Partitionen auf ${}M$ mit der Verfeinerung als Ordnung. Skizziere diese geordnete Menge.

Aufgabe

Es sei ${}M=\{a,b,c,d,e,f,g,h\}$ und es sei

${}P=\{\{a\},\{b,e,h\},\{c,g\},\{d,f\}\}\,$

eine Partition auf ${}M$. Liste sämtliche Verfeinerungen von ${}P$ auf.

Aufgabe

Es sei ${}M$ eine Menge und es sei ${}V$ die Menge aller Partitionen auf ${}M$, versehen mit der Verfeinerung von Partitionen als Relation. Zeige die folgenden Eigenschaften.

1. Die Verfeinerung ist eine Ordnung auf ${}V$.
2. ${}V$ ist ein Verband. Was ist die inhaltliche Bedeutung des Infimums und des Supremums?
3. ${}V$ ist ein beschränkter Verband.

Kommentar:

Das Hauptproblem ist hierbei, sich die Situation klar zu machen, dass die Partitionen, die ja selbst Teilmengen der Potenzmenge sind, hier als Elemente einer neuen Menge betrachten werden. Das Bildchen zu Beispiel 14.7 gibt darüber einen guten Eindruck. Wenn man sich eine Partition als eine Aufteilung einer Personenmenge in Teams vorstellt, so liegt eine Verfeinerung genau dann vor, wenn die Teams der ersten Partition eventuell weiter aufgeteilt werden, ohne dass was zusammengeführt wird (umgekehrt liegt eine Vergröberung der Partition vor, wenn Teams zusammengeschmissen werden). Es ist klar, dass eine Ordnung vorliegt.

Zum Nachweis, dass ein Verband vorliegt, müssen wir die Rolle des Infimums verstehen. Es seien also zwei Partitionen gegeben, und wir suchen die „feinste gemeinsame Vergröberung“. Wir haben also zwei Teamaufteilung, die nichts miteinander zu tun haben, und diese Teams müssen jeweils als Ganzes in ein gemeinsames Team überführt werden. Wenn eine Teilmenge bei beiden Partitionen ein Team ist, kann man dieses Team direkt übernehmen. Wenn sich ein Team der ersten Aufteilung aus Teams der zweiten Aufteilung zusammensetzt, so müssen wir dieses Team übernehmen. Im Allgemeinen ist die neue Teambildung aber schwieriger. Wenn ein Team aus der ersten Aufteilung und ein Team aus der zweiten Aufteilung sich überschneiden, also ein gemeinsames Element haben, so müssen diese beide Teams als Ganzes zu einem neuen Team gehören. Diese Vereinigung kann auch um ein paar Ecken passieren. Deshalb ist der neue Block, der ein Element ${}x$ enthält, gleich

${}[x]={\left\{y\in M\mid {\text{ es gibt Blöcke }}A_{1},\ldots ,A_{s}{\text{ von }}P_{1}{\text{ und Blöcke }}B_{1},\ldots ,B_{s-1}{\text{ von }}P_{2}{\text{ mit }}x\in A_{1}{\text{ und }}y\in A_{s}{\text{ und }}A_{i}\cap B_{i}\neq \emptyset \right\}}\,.$

 

Aufgabe

Es sei ${}M$ eine Menge und es sei ${}V$ der Verband der Partitionen auf ${}M$. Was sind die Atome von ${}V$?

Aufgabe

Es sei ${}M$ eine Menge und es sei ${}V$ der Verband der Partitionen auf ${}M$.

1. Ist ${}V$ komplementär?
2. Ist ${}V$ distributiv?
3. Ist ${}V$ boolesch?

Aufgabe

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

1. ${}B_{n}=\sum _{k=1}^{n}S({n},{k})\,.$

2. ${}B_{n+1}=\sum _{i=0}^{n}{\binom {n}{i}}B_{i}\,.$

Aufgabe

Bestimme die Bellzahlen für

${}n=0,1,2,3,4,5\,.$

Aufgabe

Schreibe ein Computerprogramm, dass die Bellzahlen ${}B_{n}$ berechnet.

Aufgabe

Zeige, dass für die Bellzahlen und die Stirlingzahlen zweiter Art die Abschätzungen

${}{\frac {B_{n}}{n}}\leq \operatorname {max} \left(S({n},{k}){|}k=1,\ldots ,n\right)\leq B_{n}\,$

gelten.

Aufgabe

Bestimme die Anzahl aller Partitionen auf einer zehnelementigen Menge, bei der jeder Block eine gerade Anzahl besitzt.

Aufgabe

Es seien ${}D$ und ${}W$ Mengen. Wir betrachten auf der Abbildungsmenge ${}\operatorname {Abb} \,{\left(D,W\right)}$ diejenige Relation, bei der die Abbildungen

$f,g\colon D\longrightarrow W$

in Relation stehen, wenn es eine bijektive Abbildung

$\rho \colon W\longrightarrow W$

mit

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

gibt. Zeige, dass dies eine Äquivalenzrelation ist.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}M$ eine Menge, ${}P$ und ${}Q$ seien Partitionen mit zugehörigen surjektiven Abbildungen

$f\colon M\longrightarrow \{1,\ldots ,k\}$

bzw.

$g\colon M\longrightarrow \{1,\ldots ,m\}$

im Sinne von Bemerkung 14.4. Zeige, dass ${}P$ genau dann eine Verfeinerung von ${}Q$ ist, wenn es eine Faktorisierung von ${}g$ über ${}f$ gibt, wenn es also eine Abbildung

$h\colon \{1,\ldots ,k\}\longrightarrow \{1,\ldots ,m\}$

mit ${}g=h\circ f$ gibt.

Aufgabe (5 Punkte)

Es sei ${}M$ eine Menge mit ${}n$ Elementen und es sei ${}V$ die Menge aller Partitionen auf ${}M$, versehen mit der Verfeinerung ${}\preccurlyeq$ von Partitionen als Ordnungsrelation. Es sei

${}P_{1}\preccurlyeq P_{2}\preccurlyeq \ldots \preccurlyeq P_{s-1}\preccurlyeq P_{s}\,$

eine endliche Folge von Partitionen auf ${}M$ mit echten Verfeinerungen, die man weder nach links noch nach rechts noch im Innern verfeinern kann. Zeige ${}s=n$.

Aufgabe (2 Punkte)

Beweise Lemma 14.12 aus Lemma 13.9 und umgekehrt.

Aufgabe (4 Punkte)

Bestimme die Stirlingzahlen zweiter Art ${}S({7},{3})$ mit den verschiedenen Charakterisierungen aus Satz 14.13.

Aufgabe (5 Punkte)

Es sei ${}r\in \mathbb {N}$ fixiert. Zeige, dass die Stirling-Zahlen zweiter Art ${}S({n},{n-r})$ durch ein Polynom in ${}n$ beschrieben werden.