Einführung in die Kombinatorik

Description

An elementary introduction to combinatorical mathematics. I Das kleine Einmaleins der Kombinatorik 1 Mengen 2 Einfache Anzahlaussagen 3 Das Inklusions-Exklusions-Prinzip 3.1 Das Inklusions-Exklusions-Prinzip mit Gewichten 3.2 Zahlentheoretische Anwendungen der Siebformel 3.3 Das Problème des ménages 3.4 Permanenten II Der Heiratssatz und seine Verwandten 1 Der Heiratssatz 2 Zum Heiratssatz verwandte Sätze 2.1 Die Sätze von König und Dilworth 2.2 Die Äquivalenz des Heiratssatzes mit den Sätzen von König und Dilworth 2.3 Verwandte Ergebnisse 2.4 Der Satz von Menger 3 Das Schnitt-Fluß-Theorem von Ford und Fulkerson 3.1 Gerichtete Graphen und Fluß-Netzwerke 3.2 Flußmaximierung 3.3 Flüsse, Matchings und disjunkte Wege 3.4 Der Satz von Baranyai III Orthogonale lateinische Quadrate 1 Problemstellung und Historisches 2 Grundbegriffe und erste Existenzaussagen 3 Endliche Körper 4 Der Satz von MacNeish 5 Differenzmatrizen 6 Widerlegung der Eulerschen Vermutung 7 Eine Anwendung: Authentikationscodes IV Der Satz vom Diktator 1 Problemstellung 2 Mächtige Familien 3 Auswege V Fastperiodische 0-1-Folgen 1 Die Morse-Thue-Folge 2 Fastperiodizität VI Der Satz von Ramsey 1 Die finite Version des Satzes von Ramsey 2 Die unendliche Version des Satzes von Ramsey VII Der Satz von van der Waerden 1 Arithmetische Progressionen 2 Beweis des Satzes von van der Waerden 3 Der Satz von Szemerédi 4 Ergebnisse von Schur, Rado und Deuber 5 Der Satz von Hales und Jewett VIII Codes 1 Sofort bzw. eindeutig entzifferbare Codes 2 Prüfziffersysteme 3 Fehlerkorrigierende Codes 4 Lineare Codes 5 Zyklische Codes und Polynomideale 6 BCH-Codes 7 Bemerkungen zur Implementierung IX Endliche projektive Ebenen und Räume 1 Grundlagen 2 Existenzfragen 3 Polaritäten 4 Das Freundschaftstheorem 5 Kollineationen und der Satz von Singer 6 Bögen und MDS-Codes 7 Unterebenen und Blockademengen 8 Anwendungen in der Kryptographie 9 Affine Geometrien X Blockpläne 1 Grundlagen 2 Direkte Konstruktionen 3 GDDs 4 Relative Differenzfamilien 5 Der PBD-Hüllenoperator 6 Blockpläne mit k ≤ 5 7 Auflösbare Blockpläne XI Symmetrische Blockpläne und Differenzmengen 1 Symmetrische Blockpläne: Grundlagen 2 Der Satz von Bruck, Ryser und Chowla 3 Hadamardmatrizen und Blockpläne 4 Eine rekursive Konstruktion 5 Differenzmengen und Gruppenringe 6 Multiplikatoren 7 Der Mann-Test 8 Planare Differenzmengen 9 Die Hadamardsche Ungleichung XII Partitionen 1 Formale Potenzreihen 2 Erzeugende Funktionen von Partitions-Anzahlen 3 Eulers Pentagonalzahlen-Theorem XIII Die Abzähltheorie von Pólya 1 Der Zyklenindex einer Permutationsgruppe 2 Das Lemma von Burnside 3 Der Satz von Pólya 4 Bäume und Strünke 5 Alkohole 6 Die Anzahl der Bäume auf n Punkten XIV Kombinatorische Betrachtungen topologischen Ursprungs 1 Das Königsberger Brückenproblem 2 Der Eulersche Polyedersatz 3 Der Fünffarbensatz 4 Hamiltonsche Kreise 5 Das Spernersche Lemma 6 Der Satz von Helly XV Spiele auf Graphen 1 Baumspiele 2 Das klassische Nim-Spiel 3 Spiele vom Typ Nim auf Graphen XVI Spezielle Folgen von ganzen Zahlen 1 Die Fibonacci-Zahlen 2 Die Ménage-Zahlen 3 Die Rencontres-Zahlen 4 Die Partitionszahlen 5 Die Catalan-Zahlen 6 Die Bell-Zahlen 7 Die Stirling-Zahlen zweiter Art 8 Die Stirling-Zahlen erster Art 9 Die Gauß-Koeffizienten Nachwort Literaturverzeichnis Index