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:
- M. Aigner, "Combinatorial Theory". Springer, 1997. Ein Klassiker,
in dem Sie das
Thema Posets gut aufbereitet finden.
- I. Anderson, "Combinatorics of finite sets". Oxford University Press,
1987, und Dover Publications, 2002. Relevant für das Thema Postes.
Das Buch ist sehr gut zu lesen.
- P. Flajolet, R. Sedgewick "Analytic Combinatorics''. Dieses Buch ist
noch in Arbeit. Die neuste Version finden sie hier
kostenlos. Für uns relevant sind vor allem die Kapitel I und II.
- R.L. Graham, D.E. Knuth, O.Patashnik, "Concrete Mathematics",
Addison-Weseley 1994. Die Bibel der "konkreten" Mathematik. Das
bedeutet
1) "concrete" als Gegensatz zur abstrakten Mathematik und
2) concrete=con+crete, von
continuous+discrete.
- In meinem alten Handout zum Thema "Ends
of graphs" finden Sie einiges über Cayley-graphen. Diese
Unterlagen enthalten sicher einige Tippfehler und werden im kommenden WS
überarbeitet werden. Hier bekommen Sie auch einen
Vorgeschmack auf meine VL im WS 2008/09.
- J.J. van Lint & R.M. Wilson "A Course in Enumerative Combinatorics"
2nd edition, Cambridge University Press 2001. Zur Pólya Theorie lesen
Sie Kapitel 37.
- R.P. Stanley "Enumerative Combinatorics" Vol. 1+2, Cambridge
University Press 1999. Ein umfassendes Standardwerk.
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.