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 von Wolfgang Schwarz  (wird bald veröffentlicht)

Ich bin Herrn Schwarz für die Ausarbeitung des Scriptes, 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