Kombinatorik SS2008

Die VL hat 51 mal je 50 Minuten stattgefunden, anstatt 57 mal je 45 Minuten.

VL: Mo, Di 9:10-10:00 C2.09 (UZA4); Mi, Do 10:05-11:55 2A310 (UZA2). Beginn Mo 3. März.

Meine Sprechstunde ist am Dienstag 11:00-12:00, Raum C617 (UZA4).
Soferne ich gerade Zeit habe, können Sie sich auch außerhalb der Sprechstunde jederzeit Tipps zu den Übungsbeispielen holen oder Fragen zum Vorlesungsstoff stellen. Sonstige Rücksprache via Email.

Die VL baut auf Teilen der VL "Diskrete Mathematik'' auf. Hier finden Sie ein Skriptum der VL aus dem WS 07/08. Dieses liegt auch in der Skriptenverkaufsstelle auf Level 2 im UZA4 zum Verkauf auf. Relevant ist das Kapitel 2. Wichtig sind: elementare Kombinatorik mit Binomialkoeffizienten, Fibonacci-Zahlen, erzeugende Funktionen und formale Potenzreihen. Zum Thema Lösen von linearen Rekursionen sehen Sie sich am besten das Beispiel 2.19 in Kapitel 2.3 ab Seite 61 an, in dem eine "Standard-Methode" illustriert wird.

Die aktuellen Übungsbeispiele finden Sie hier.

Ein Beispiel, das wir in der VL besprechen: Die hundert Gefangenen.

Für die Vorlesung in Kombinatorik müssen sie sich keine Bücher kaufen, die Vorlesungsmitschrift reicht aus. Folgenede Literatur kann aber als Ergänzung dienen: Hier finde Sie eine VL-Mitschrift von Christoph Marx.


Folgende Kapitel wurden in der VL behandelt

0 Einleitung
0.1 Wie beweist man kombinatorische Aussagen?
0.2 Anzahl disjunkter k-Tupel von Teilmengen
0.3 Spannbäume in speziellen Graphenklassen
0.4 Rechnen mit Potenzreihen

1 Kombinatorische Klassen und ihre erzeugenden Funktionen, ungelabelte Objekte
1.1 Formale Potenzreihen
1.2 Ungelabelte kombinatorische Klassen
1.3 Vereinigung
1.4 Produkt
1.5 Folgen
1.6 Multimengen
1.7 Potenzmengen
1.8 Zusammensetzung von Potenzreihen
1.9 Die Lagrangesche Inversionsformel

2 Gelabelte Klassen
2.1 Spezielle gelabelte Klassen
2.2 Gelabeltes Produkt
2.3 Folgen, Mengen und Zyklen
2.4 Surjektionen
2.5 Mengenpartitionen
2.6 Permutationen
2.7 Gelabelte Bäume
2.8 Wörter als gelabelte und ungelabelte Objekte

3 Pólya Theorie
3.1 Gruppentheoretische Grundlagen
3.2 Gruppenaktionen
3.3 Das Lemma von Burnside
3.4 Aktionen auf Mengen von gefärbten Objekten
3.5 Der Zyklenzeiger
3.6 Zyklenzeiger und Gewichtsfunktionen
3.7 Kombinierte Gruppenaktionen

4 Partiell geordnete Mengen
4.1 Grundbegriffe Posets
4.2 Grundbegriffe Verbände
4.3 Der Satz von Sperner
4.4 Der Satz von Dilworth
4.5 Eine Anwendung: Der Heiratsssatz
4.6 Die Inzidenzalgebra
4.7 Möbius-Inversion
4.8 Anwendungen der Möbius-Inversion

Prüfungsmodus: mündliche Prüfung. Abgesehen von dem Stoff der VL werden Beispiele gefragt, die in ihrer Art ähnlich zu den in der VL besprochenen Beispielen sind.

Ein paar typische Überblicksfragen könnten so aussehen:
  • Formale Potenzreihen, kombinatorische Klassen und Klassenopertoren
  • Wann betrachtet man gelabelte und wann ungelabelte Klassen? Was sind die Unterschiede? Beispiele
  • Das gelabelte Produkt
  • Catalan- und Fibonacci-Zahlen; Definition, Beispiele, erzeugende Funktionen etc.
  • Surjektinen und Partitionen
  • Abzählen von Bäumen (vollständige, ebene, gewurzelte, gelabelte, Satz von Cayley)
  • Gruppenaktionen und Lemma von Burnside
  • Was sind Zyklenzeiger und wozu sind sie gut?
  • Gruppenaktionen auf gelabelten Objekten
  • Erklähren Sie kombinierte Gruppenaktionen allgemein und anhand von Beispielen.
  • Allgemeine Sätz über Posets und Anwendungen
  • Was ist die Möbius-Funktion eines Posets? Methoden der Berechnung und Anwendungen
  • Diese Liste kann sich jederzeit ändern und dient lediglich als Hilfe für die Vorbereitung.
    Prüfungsstoff ist der in der VL besprochen Stoff.

    Bei folgenden Beweisen genügt es, sie unter Verwendung von Unterlagen zu erklären: Lagrange-Inversion, Hauptsatz über kombinierte Gruppenaktionen (Zyklenzeiger-Formel).

    Nicht geprüft werden: Konstruktion und Definition von freien Gruppen und Gruppenpräsentationen. Sie sollten jedoch Gruppenpräsentationen und Cayley-Graphen zumindest von einfachen Beispielen von Gruppen bestimmen bzw. interpretieren können.

    Beispiele aus dem PS, die Sie sich ansehen sollten, da sie dem VL-Stoff besonders nahe sind: 4-9, 23-25, 31-34, 37-45, 53, 56, 57, 59, 63, 64.

    Zurück zur Startseite.