Inhaltsverzeichnis
Diskrete Strukturen I -- Kombinatorik
Sommersemester 2005
Stefan Felsner
Vorlesungsdetails:
1 ,
2 ,
3 ,
4 ,
5 ,
6 ,
7 ,
8 ,
9 ,
10 ,
11 ,
12 ,
13 ,
14 ,
15 ,
16 ,
17 ,
18 ,
19 ,
20 ,
21 ,
22 ,
23 ,
24 ,
1. Vorlesung, Mi. 20.4.2005
Propädeutik
Permutationen
Inversionen, die Zahlen ( in(k) )
Fixpunktfreie Permutationen
(Derangements)
Orthogonale Lateinische Quadrate
(Eulers Offiziersproblem)
2. Vorlesung, Do. 21.4.2005
Orthogonale Lateinische Quadrate und Projektive Ebenen
(Eulers Offiziersproblem)
OLQ Paare aus Gruppen für ungerade Ordnung n
Für jede Ordnung n gibt es <= n-1 paarweise OLQ
Mengen von paarweise OLQ und projektive Ebenen
Konstruktion projektiver Ebenen aus Körpern
3. Vorlesung, Mi. 27.4.2005
Permutationen
Darstellungen: Zweizeilig, einzeilig (Wort), Zyklen
Standardzyklendarstellung -> Links-Rechts Maxima
Zyklenvektor und Typ
c(n,k) Anzahl Permutationen mit k-Zyklen
Rekursion und erzeugende Funktion fuer c(n,k)
4. Vorlesung, Do. 28.4.2005
Erwartete Anzahl von Zyklen, zwei Beweise
Harmonische Zahlen
Doppeltes Abzählen
Erwartete Anzahl von Teilern
Noch eine Transposition
5. Vorlesung, Mi. 4.5.2005
Die 12 Arten des Zählens
verschieden Bijektionen
Mengenpartitionen
Stirling Zahlen beider Arten
6. Vorlesung, Mi. 11.5.2005
Partitionen einer Zahl
Darstellungen und die Konjugierte
Erzeugende Funktion
Hardy-Ramanujan-Rademacher Entwicklung von p(n)
#Part. v. n in verschiedene Teile = #Part. v. n in ungerade Teile
Pentagonalzahlensatz von Euler
7. Vorlesung, Do. 12.5.2005
Formale Potenzreihen
FPRs und Konvergenz
Multiplikative Inverse
Beispiel: Bernoulli Zahlen
Beispiel: Derangements
Inverse
8. Vorlesung, Mi. 18.5.2005
Kombinatorik endlicher Mengen
Kardinalität von intersecting families
Boolscheverbände; Ordnungen und Verbände
Satz von Sperner und LYM-Ungleichung
Satz von Erdös-Ko-Rado
9. Vorlesung, Do. 19.5.2005
Kleine maximale k-intersecting families
Konstruktion aus projektiven Ebenen
Untere Schranke
Schattenargumente
Sperners Beweis für seinen Satz
10. Vorlesung, Mo. 23.5.2005
Satz von Kruskal-Katona
Zahlendarstellung
Ungekehrt lexikographische Ordnung
Shift-Operator und Schatten
11. Vorlesung, Mi. 25.5.2005
Folgerungen aus Kruskal-Katona
Satz von Erdös-Ko-Rado
f-Vektoren von Simplizialkomplexen
Antiketten
Dualitätssätze
Heiratssatz (Satz von Hall)
Satz von König-Egervary
12. Vorlesung, Mi. 1.6.2005
Satz von Dilworth
Symmetrischen Kettenzerlegungen
Für Bn
Für Multimengenverbände
13. Vorlesung, Do. 2.6.2005
Klammerregel zur Berechnung der Kette einer Menge
Anwendung: Obere Schranke für Dedekind Zahlen (A000372)
Ordnungen und Verbände
Verbände
14. Vorlesung, Mi. 8.6.2005
Distributive Verbände
Hauptsatz für endliche distributive Verbände
Lineare Erweiterungen und Dimension
Existenz von linearen Erweiterungen
Lineare Erweiterungen und Ketten im Idealverband
(Vorlesungsmitschrift: Ordnungen und Dimension)
15. Vorlesung, Do. 9.6.2005
Dimension einer Ordnung
Definitionen von Dushnik-Miller und Ore
Standardbeispiel und Dimension von Bn
Dimension distributiver Verbände (Dilworth)
Schranken für die Dimension
Dimension 2 und konjugierte Ordnungen
16. Vorlesung, Mi 15.6.2005
Robinson-Shensted-Knuth Korrespondenz
Young-Tableaux
Die zentrale Bijektion
Beweis a la Viennot:
Sprunglinien und Skelette
Erzeugen ein Tableau
Umkehrung
Die Greene-Kleitman Saetze ueber Ordnungen
Der 2-dimensionale Fall
Weiteres ueber Tableaux und RSK
17. Vorlesung, Mi 22.6.2005
Inzidenz Algebra einer Ordnung
Zeta-Funktion und zählen von Ketten
Möbius Inversion
Berechnen von Möbius-Funktionen
Ketten - Produkte - Boolsche Verbände
Das Prinzip der Inklusion und Exklusion
Derangements
18. Vorlesung, Do 23.6.2005
Surjektive Funktionen
#Part. v. n in verschiedene Teile = #Part. v. n in ungerade Teile
(ein dritter Beweis)
Explizite Darstellung der Phi-Funktion
Möbius-Funktion von Multimengen- resp. Teilerverbänden
Phi-Funktion und Möbius-Funktion
Der Kettenkomplex einer Ordnung
Möbius-Funktion und Euler Charakteristik
19. Vorlesung, Mi 29.6.2005
Zählen von Isomorphieklassen - Polya Theorie
Typische Probleme
Permutationsgruppen und induzierte Wirkung
Bahnen und Stabilisatoren
Lemma von Burnside-Frobenius
Anwendungen des Lemmas
20. Vorlesung, Do 30.6.2005
Zyklenindex einer Permutation
Zyklenindikator
Bahnen von k-Teilmengen
Zyklen-Index-Theorem
21. Vorlesung, Mi 6.7.2005
1-Faktorisierungen
Existenz im Falle K2n
Struktur und Anzahl Falle K6
Blockpläne (Designs)
Definition
Beispiele - triviale, Fano Ebene
- S(3,4,2n) aus Vektoraddition über F2
- ein S6(3,5,10) aus Kantenbahnen des K5
22. Vorlesung, Do 7.7.2005
Blockzahlen und arithmetische Bedingungen
Das Wiederholungszahlendreieck
Die projektive Ebene der Ordnung 4 aus K6
23. Vorlesung, Mi 13.7.2005
Catalan Zahlen
Catalan familien und Bijektionen
Das Spiegelungsprinzip
Geklammerte Permutationen
24. Vorlesung, Mi 14.7.2005
Catalan Zahlen und zyklische +1, -1 Strings
Erzeugende Funktion
Catalan Ordnungen
Tamari Verband, Assoziaeder und Rotationsdistanz
Der Wegeverband
Conways Dameproblem
Zurück zur
Vorlesungsseite.