Algorithmische Kombinatorik

Peter Paule
326.246, WS 2000/2001
Mi 8:30-10:00, T 711, Start: 11.10.2000

Notwendige Vorkenntnisse

Analysis I & II, Lineare Algebra I & II

Ziele der Lehrveranstaltung

Vermittlung der algorithmischen Grundwerkzeuge für das Lösen von Abzählproblemen.

Inhalt der Lehrveranstaltung

Enumerative Kombinatorik zerfällt i.w. in zwei Problemkreise: in Abzähltheorie (liefert Anzahlformeln, z.B. kompliziert gebaute Summationen) und in Techniken zur Formel-Manipulation (z.B. zur Vereinfachung von Summen über Binomialkoeffizienten).

Der Schwerpunkt der Vorlesung liegt auf Abzähltechniken im allgemeinen, unter Berücksichtigung von konstruktiven Techniken (Computeralgebra). Im ersten Teil der Vorlesung wird in die wichtigsten Grundbegriffe der Kombinatorik eingeführt (erzeugende Funktionen, spezielle Zahlfolgen wie etwa Stirlingzahlen, Rekursionen, u.s.w.).

Im zweiten Teil der Vorlesung wird auf verschiedene Probleme der algebraischen Abzähltheorie eingegangen, z.B. Konstruktion bzw. Auflistung kombinatorischer Objekte wie etwa Permutationen, Partitionen oder Graphen. Insbesondere wird in Grundlagen der sog. Polya-Theorie eingeführt. (Typische Anwendungen behandeln z.B. verschiedene Färbungen geometrischer Objekte oder das Abzählen von chemischen Molekülen.)

Literatur

Neben Originalarbeiten werden Abschnitte aus folgenden Büchern diskutiert:

• A. Kerber: "Algebraic Combinatorics via Finite Group Action", BI-Wiss.-Verl., 1991
• D. Stanton, D. White: "Constructive Combinatorics", Springer Undergraduate Texts in Mathematics, 1986
• S. Skiena, "Implementing Discrete Mathematics (Combinatorics and Graph Theory with Mathematica)", Addison-Wesley, 1990.