Diskrete Algebraische Strukturen

Markus Junker Universit "at Freiburg

Sommersemester 1999

Inhaltsverzeichnis ENDLICHE KOMBINATORIK 5

Mengen, Abbildungen, Partitionen . . . . . . . . . . . . . . . . . . . . . . . . . 5

Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Teilmengen und Binomialkoeffizienten . . . . . . . . . . . . . . . . . . . . 7 Mengenpartitionen und Stirling-Zahlen zweiter Art . . . . . . . . . . . . . 9 Zahlpartitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Geordnete Zahlpartitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Kleine Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Permutationen und Stirling-Zahlen erster Art . . . . . . . . . . . . . . . . 12

Diskrete Wahrscheinlichkeitstheorie . . . . . . . . . . . . . . . . . . . . . . . . 14

Bedingte Wahrscheinlichkeit . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Produktr "aume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Zufallsvariablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Erwartungswert und Varianz . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Erzeugende Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Formale Potenzreihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Zwei einfache Rekursionsgleichungen . . . . . . . . . . . . . . . . . . . . . 19 L "osungsverfahren f "ur lineare Rekursionsgleichungen endlicher Ordnung . . 20 Eine nicht lineare Rekursionsgleichung . . . . . . . . . . . . . . . . . . . . 22 Exponentielle erzeugende Funktionen . . . . . . . . . . . . . . . . . . . . . 23 Anwendung auf die Bell-Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 23 Noch ein Beispiel ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Gr "ossenwachstum von Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3

M. Junker Diskrete Algebraische Strukturen GRAPHEN 27

Definition und Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Darstellungen von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Varianten von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Anzahl der Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Wege, Abstand, Zusammenhang . . . . . . . . . . . . . . . . . . . . . . . . 30

Besondere Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Euler-Z "uge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Hamiltonsche Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Problem des Handlungsreisenden . . . . . . . . . . . . . . . . . . . . . . . 33 K "urzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

F"arbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Eckenf "arbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Kantenf "arbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Der Satz von Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36