V42 - Abzählende Kombinatorik - Material

Vorlesung: 

Abzählende Kombinatorik

von Prof. Dr. Stephan Klaus

Fachbereich Mathematik, Universität Mainz, Sommersemester 2022

Material zur Vorlesung:

• Ankündigung der Vorlesung (PDF)
• Skript (PDF) von Wolfgang Schwarz

Ich bin Herrn Schwarz für die Ausarbeitung des Skriptes, das er mit vielen Details und weiteren Informationen bereichert hat, sehr dankbar!

Inhaltsverzeichnis der Vorlesung:

1. Erzeugende Funktionen
2. Formale Potenzreihen
3. Geordnete Partitionen
4. Ungeordnete Partitionen
5. Stirling-Zahlen und Bell-Zahlen
6. Catalan-Zahlen
7. Der Abzählsatz von Polya

Stichworte zum Stoff der Vorlesung:

1. Erzeugende Funktionen

• Erzeugende Funktion (EF) einer Folge von Zahlen oder endlicher Mengen
• Teilmengen
• Multimengen
• Exponentiell erzeugende Funktionen (EEF)
• Ableitung und Integral
• Hadamard-Produkt

2. Formale Potenzreihen

• Formale Potenzreihen über einem kommutative Ring
• Ringstruktur
• Ordnung einer formalen Potenzreihe
• Abzählbare Summen
• Komposition
• Abzählbare Produkte
• Ableitung und Integral

3. Geordnete Partitionen

• Geordnete Partitionen
• Spezielle geordnete Partitionen
• Multiple geordnete Partitionen und Wörter
• Fibonacci-Zahlen
• Der goldene Schnitt
• Asymptotik der Fibonacci-Zahlen
• Fibonacci-Zahlen höherer Ordnung

4. Ungeordnete Partitionen

• Ungeordnete Partitionen
• Ferrer-Diagramme
• Dualität
• Spezielle ungeordnete Partitionen
• Multiple ungeordnete Partitionen und Monome
• Partitionen mit Wiederholung ("bosonisch"): p_n
• Partitionen ohne Wiederholung ("fermionisch"): q_n
• Selbstduale Partitionen: d_n
• Satz: p^odd_n = q_n  (# bosonische ungerade Partitionen  = # fermionische Partitionen)
  
• Satz: q^odd_n = d_n  (# fermionische ungerade Partitionen  = # selbstduale Partitionen)
• Eulersches Pentagonalzahl-Theorem
• Rekursionsformel für Partitionen

5. Stirling-Zahlen und Bell-Zahlen

• Mengenpartitionen und Äquivalenzrelationen
• Stirling-Zahlen 2. Art
• Bell-Zahlen
• Spezielle Werte
• Rekursionsformel für Stirling-Zahlen 2. Art
• EEF der Stirling-Zahlen 2. Art
• EEF der Bell-Zahlen
• Summenformel für Stirling-Zahlen 2. Art
• Rekursionsformel für Bell-Zahlen
• Analytische Formel für Bell-Zahlen
• Anzahl aller surjektiven Abbildungen von endlichen Mengen
• Absteigende Potenzen x^↓n
• Stirling-Zahlen 2. Art und Basiswechsel von xⁿ zu x^↓n
• Stirling-Zahlen 1. Art und Basiswechsel von x^↓n zu xⁿ
• Stirling-Zahlen 1. Art und Permutationen mit k Zykeln
• Der 12-fache Weg

6. Catalan-Zahlen

• Klammerungen von Produkten und Catalan-Zahlen
• Rekursionsformel
• Explizite Formel
• Ebene binäre Bäume mit Wurzel
• Dyck-Worte und Gitter-Pfade
• Triangulierungen konvexer Polygone
• Ebene triadische Bäume mit Wurzel
• Anwendung in der Chemie: markierte Kohlenwasserstoffe

7. Der Abzählsatz von Polya

• Gruppenoperationen
• Orbitzerlegung
• Stabilisator
• Linksnebenklassen, homogene Räume und Satz von Lagrange
• Fixpunktmengen
• Lemma von Burnside
• Beispiel: Färbungen des Würfels
• Zykelindikator
• Abzählsatz von Polya