Blatt 5 SS00

Prof. Laue

Abgabe 7.06.2000

Aufgabe 6 (4+3+2+3)

In der Vorlesung wurden Partitionen eingeführt. Man kann sie mit dem sogenannten Ferrers Diagramm visualisieren. So gehört das Diagramm

 --------------
|    |    |    |
|    |    |    |
 --------------
|    |    |
|    |    |
 ---------

zur Partition 3,2.   Zu dieser Partition kann man eine 0-1 Folge zuordnen indem man rechts oben beginnt und sich am Rahmen des Diagramms nach links unten entlang bewegt. Dabei macht man Schritte nach links oder Schritte nach unten. Schritte nach links kodiert man mit 1 Schritte nach unten mit 0. Obige Partition wäre dann die Folge 1........1 0  1 0 1 1 0 ............. 0. Führende Einsen und Nullen am Ende sind nicht signifikant.  Verwenden Sie diese Idee um eine Bijektion zwischen Partitionen innerhalb eines Rechtecks (mit k Zeilen und n Spalten) und n-elementigen Teilmengen einer (n+k) elementigen Grundmenge zu definieren. (4 Punkte)
Erstellen Sie eine Liste der bijektiv verknüpften Partitionen innerhalb eine 3x3 Rechtecks und der zugehörigen Teilmengen. (3 Punkte)
Partitionen können durch "enthalten sein" partiell geordnet werden.  Obige Partition 3,2 ist grösserer Nachbar zu 3,1 und 2,2 und kleinerer Nachbar zu 4,2 3,3 und 3,2,1. Zeichen Sie das zugehörige Hassediagramm für die Partitionen innerhalb des 3x3 Rechtecks (2 Punkte).  Im Beispiel des 2x2 Rechtecks wäre es folgendes Diagramm: