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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe Referenznummer erstellen

Zeige, dass die Anzahl der geordneten Partitionen mit eventuell leeren Blöcken zum Anzahltupel einer -elementigen Menge gleich

ist.


Aufgabe Referenznummer erstellen

Bestimme die Stirlingzahlen zweiter Art für .


Aufgabe Referenznummer erstellen

Es sei fixiert. Zeige, dass die Stirling-Zahlen zweiter Art ein Polynom in vom Grad ist.


Aufgabe Referenznummer erstellen

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


Es sei eine Menge und und seien Partitionen von . Man sagt, dass feiner als ist, wenn jeder Block von eine Teilmenge eines Blockes von ist.


Aufgabe Referenznummer erstellen

Es sei und es sei die Menge der Partitionen auf mit der Verfeinerung als Ordnung. Skizziere diese geordnete Menge.


Aufgabe Referenznummer erstellen

Es sei und es sei

eine Partition auf . Liste sämtliche Verfeinerungen von auf.


Aufgabe Referenznummer erstellen

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

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


Aufgabe Referenznummer erstellen

Es sei eine Menge und es sei der Verband der Partitionen auf . Was sind die Atome von ?


Aufgabe Referenznummer erstellen

Es sei eine Menge und es sei der Verband der Partitionen auf .

  1. Ist komplementär?
  2. Ist distributiv?
  3. Ist boolesch?


Aufgabe Aufgabe 14.10 ändern

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


Aufgabe Referenznummer erstellen

Bestimme die Bellzahlen für


Aufgabe Referenznummer erstellen

Schreibe ein Computerprogramm, dass die Bellzahlen berechnet.


Aufgabe Referenznummer erstellen

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

gelten.


Aufgabe Referenznummer erstellen

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


Aufgabe Aufgabe 14.15 ändern

Es seien und Mengen. Wir betrachten auf der Abbildungsmenge diejenige Relation, bei der die Abbildungen

in Relation stehen, wenn es eine bijektive Abbildung

mit

gibt. Zeige, dass dies eine Äquivalenzrelation ist.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)Referenznummer erstellen

Es sei eine Menge, und seien Partitionen mit zugehörigen surjektiven Abbildungen

bzw.

im Sinne von Bemerkung 14.4. Zeige, dass genau dann eine Verfeinerung von ist, wenn es eine Faktorisierung von über gibt, wenn es also eine Abbildung

mit gibt.


Aufgabe (5 Punkte)Referenznummer erstellen

Es sei eine Menge mit Elementen und es sei die Menge aller Partitionen auf , versehen mit der Verfeinerung von Partitionen als Ordnungsrelation. Es sei

eine endliche Folge von Partitionen auf mit echten Verfeinerungen, die man weder nach links noch nach rechts noch im Innern verfeinern kann. Zeige .


Aufgabe (2 Punkte)Referenznummer erstellen

Beweise Lemma 14.12 aus Lemma 13.9 und umgekehrt.


Aufgabe (4 Punkte)Referenznummer erstellen

Bestimme die Stirlingzahlen zweiter Art mit den verschiedenen Charakterisierungen aus Satz 14.13.


Aufgabe (5 Punkte)Referenznummer erstellen

Es sei fixiert. Zeige, dass die Stirling-Zahlen zweiter Art durch ein Polynom in beschrieben werden.