Skip to main content
main-content

Über dieses Buch

Dieses Lehrbuch vermittelt die Grundlagen und Konzepte der modernen Kombinatorik in anschaulicher Weise. Die verständliche Darlegung richtet sich an Studierende der Mathematik, der Naturwissenschaften, der Informatik und der Wirtschaftswissenschaften und erlaubt einen einfachen und beispielorientierten Zugang zu den Methoden der Kombinatorik. Beginnend mit den Grundaufgaben der Kombinatorik wird der Leser Schritt für Schritt mit weiterführenden Themen wie erzeugende Funktionen, Rekurrenzgleichungen und der Möbiusinversion sowie Graphenpolynomen und endlichen Automaten vertraut gemacht. Eine Vielzahl von Beispielen und Übungsaufgaben mit Lösungen erleichtern das Verständnis und dienen der Vertiefung und praktischen Anwendung des Lehrstoffes.

Die vorliegende dritte Auflage ist komplett durchgesehen und deutlich erweitert um das Thema Kombinatorische Klassen und weitere, auch für die praktische Anwendung wichtige Graphenpolynome.

Inhaltsverzeichnis

Frontmatter

1. Abzählen von Objekten

Zusammenfassung
Ein Grundproblem der Kombinatorik ist das Abzählen der Elemente einer gegebenen endlichen Menge. Die Elemente dieser Menge sind kombinatorische Objekte, wie zum Beispiel Anordnungen (Permutationen), Auswahlen (Kombinationen, Variationen), Verteilungen und Zerlegungen (Partitionen). Eine Methode, die sich prinzipiell immer für derartige Anzahlprobleme eignet, ist das explizite Auflisten (die Enumeration) aller Objekte der Menge. Praktisch stößt dieses Verfahren jedoch schnell an Grenzen, die aus dem für die Auflistung erforderlichen Zeitaufwand resultieren. Ein weiterer Grund, der gegen dieses Verfahren spricht, ist die geringe Aussagekraft einer durch Auflistung gefundenen Lösung. Häufig ist man vielmehr an einer allgemeingültigen Formel für die Anzahl gewisser kombinatorischer Objekte als an der Mächtigkeit einer ganz konkreten Menge interessiert. Die Lösung kombinatorischer Anzahlprobleme führt zu speziellen Folgen ganzer Zahlen. Dazu zählen die Fakultät, Binomialkoeffizienten, Stirling-Zahlen erster und zweiter Art sowie viele weitere bekannte Zahlenfolgen.
Peter Tittmann

2. Erzeugende Funktionen

Zusammenfassung
Erzeugende Funktionen sind eines der leistungsfähigsten Werkzeuge der Kombinatorik. Sie bilden ein Bindeglied zwischen Problemen der diskreten Mathematik und Methoden der Analysis. Die Lösung von Aufgaben der Kombinatorik mit erzeugenden Funktionen erfordert den Umgang mit Potenzreihen. Die notwendigen Grundlagen des Rechnens mit formalen Potenzreihen werden im zweiten Abschnitt eingeführt. Zunächst stellen wir jedoch einige Anwendungen erzeugender Funktionen an Beispielen vor.
Peter Tittmann

3. Rekurrenzgleichungen

Zusammenfassung
Rekurrente Gleichungen sind Gleichungen, in denen eine Funktion einer ganzzahligen Variablen in Abhängigkeit derselben Funktion anderer Argumente dargestellt ist. In günstigen Fällen gelingt es, eine explizite Darstellung der Funktion aus der Rekurrenzgleichung abzuleiten. Bevor wir verschiedene Lösungsmethoden erläutern, zeigt der folgende Abschnitt zunächst, wie aus kombinatorischen Problemen Rekurrenzgleichungen entstehen. Den Schwerpunkt dieses Kapitel bilden lineare Rekurrenzgleichungen; der letzte Abschnitt liefert einen ersten Einblick in spezielle nichtlineare Gleichungen.
Peter Tittmann

4. Summen

Zusammenfassung
Die Berechnung von Summen ist oft trickreich. Für eine größere Klasse von Summenformeln gibt es jedoch eine einheitliche Theorie, die auf der Operatorenrechnung basiert. Neben einigen elementaren Methoden wird deshalb die Theorie der Differenzen- und Summenoperatoren der Hauptgegenstand der folgenden Darlegungen sein. Differenzen und Summen weisen eine enge Verwandtschaft zu den aus der Analysis bekannten Begriffen Ableitung und Integral auf. Viele in der Kombinatorik auftretende Summen lassen sich heute bereits automatisch mit der Hilfe von Computeralgebrasystemen lösen. Trotz dieser Fortschritte sind die hier vorgestellten Methoden nicht überflüssig. Sie liefern nicht nur einen Einblick in die klassische Summationstheorie, sondern bieten häufig auch mehr Verständnis für das Problem als ein automatisch geführter Beweis für eine Summenformel.
Peter Tittmann

5. Graphen

Zusammenfassung
Graphen treten als mathematische Beschreibungsform für eine Vielzahl unterschiedlicher Anwendungen auf. Dazu zählen Molekülstrukturen, Computernetze, neuronale Netze, Kombinationsmöglichkeiten von DNA-Sequenzen und viele weitere. In all diesen Gebieten treten auch kombinatorische Probleme auf. Eine Frage dieser Art ist: Wie viel Isomere einer gegebenen chemischen Verbindung gibt es? Diese Frage führt auf das Problem der Anzahlbestimmung von Graphen. In der Informatik haben Graphen spezieller Struktur (Bäume) eine große Bedeutung. Auch hier ist die Anzahlbestimmung von Bäumen mit bestimmten Eigenschaften wichtig, um zum Beispiel Aussagen über die Komplexität von Such- oder Sortieralgorithmen zu erhalten. Andererseits bilden die Graphen auch innerhalb der Kombinatorik ein wesentliches Werkzeug. Sie ermöglichen die Beschreibung von Permutationen, geordneten Mengen oder Abbildungen.
Peter Tittmann

6. Geordnete Mengen

Zusammenfassung
Geordnete Mengen und Inzidenzfunktionen bilden ein wesentliches Werkzeug für die enumerative Kombinatorik. Der Gegenstand des ersten Abschnitts sind Grundbegriffe und wesentliche Aussagen der Ordnungstheorie. Für ein tieferes Studium der Ordnungstheorie sind die Bücher Stanley (1997) und Aigner (1975) sehr zu empfehlen. Wir werden uns hier auf die Untersuchung endlicher Mengen beschränken. Im weiteren werden dann spezielle geordnete Mengen, die Verbände, im Vordergrund der Betrachtungen stehen. Die Brücke zu den Anwendungen in der Kombinatorik bildet schließlich eine Klasse von Funktionen, die auf einer geordneten Menge definiert sind. Hierbei erweist sich die Möbius-Funktion als besonders nützlich. Als Anwendung der Möbius-Inversion wird das Inklusions-Exklusions-Prinzip – eine grundlegende Methode zur Abzählung kombinatorischer Objekte – vorgestellt.
Peter Tittmann

7. Kombinatorische Klassen – Ein allgemeiner Zugang zu erzeugenden Funktionen

Zusammenfassung
In diesem Kapitel werden wir erzeugende Funktionen von einem allgemeineren Standpunkt betrachten. Zunächst werden wir genau definieren, welche Voraussetzungen erforderlich sind, um Objekte einer (allgemein unendlichen) Menge zählen zu können. Dazu führen wir sogenannte kombinatorische Klassen nach einer Idee von Philippe Flajolet ein. Dann werden wir untersuchen, wie man mit kombinatorischen Klassen operieren kann, um neue kombinatorische Objekte zu erzeugen. Wir können zum Beispiel aus einer gegebenen Klasse von kombinatorischen Objekten eine neue Klasse durch Bildung von Teilmengen, geordneten Paaren oder Listen erzeugen. Dabei wird sich zeigen, dass viele wichtige Operationen mit kombinatorischen Klassen in äquivalente Operationen mit erzeugenden Funktionen übersetzt werden können. Wir erhalten damit einen sehr allgemeinen und eleganten Zugang zu vielen Fragen der enumerativen Kombinatorik.
Peter Tittmann

8. Permutationen

Zusammenfassung
Wir haben bisher verschiedeneMethoden zur Anzahlbestimmung kombinatorischer Objekte kennengelernt. Einen wesentlichen Aspekt des Abzählens beherrschen wir jedoch noch nicht – die Symmetrie. Wie zählen wir kombinatorische Konfigurationen (Graphen, Permutationen, Partitionen, Wörter, ...), wenn zwei Konfigurationen, die symmetrisch zueinander sind, als nicht unterscheidbar angesehen werden? Eine Symmetrie entsteht zum Beispiel dann, wenn eine Konfiguration bei einer Drehung (einem zyklischen Tausch) oder einer Spiegelung erhalten bleibt. In diesem Kapitel werden die Grundlagen aus der Theorie der Symmetriegruppen sowie die Abzähltheorie und ihre Anwendungen in der Kombinatorik vorgestellt.
Peter Tittmann

9. Abzählen von Graphen und Bäumen

Zusammenfassung
Die Bestimmung der Anzahl einer speziellen Klasse von Graphen liefert interessante Beispiele für die Anwendung der in den ersten Kapiteln betrachteten Methoden der Kombinatorik. Neben erzeugenden Funktionen und Rekurrenzgleichungen werden wir speziell auch auf Methoden der Gruppentheorie zurückgreifen. Die erste Frage, die wir hier näher untersuchen werden, ist: Wie viel Graphen mit n Knoten gibt es? Die Lösung dieses Problems wird jedoch erst möglich, wenn klar ist, was wir unter einem Graphen verstehen. Beschränken wir uns auf schlichte ungerichtete Graphen, so bleibt immer noch zu klären, wann zwei Graphen als identisch angesehen werden. Für viele Probleme der Graphentheorie werden zueinander isomorphe Graphen identifiziert. Wir sprechen dann von einer Isomorphieklasse von Graphen.
Peter Tittmann

10. Wörter und Automaten

Zusammenfassung
Viele Probleme der enumerativen Kombinatorik lassen sich durch formale Sprachen charakterisieren, die durch Mengen von verbotenen Unterwörtern gekennzeichnet sind. Ist die Menge der verbotenen Unterwörter endlich, so erhalten wir eine reguläre Sprache. Die erzeugende Funktion für die Anzahl der Wörter der Länge n einer regulären Sprache ist stets rational. Sie lässt sich mit einem endlichen Automaten durch Reduktionstechniken bestimmen. Die Konstruktion dieser Automaten und ihre Anwendung zur Lösung von Anzahlproblemen wird hier näher beschrieben. Durch den Übergang zu unendlichen Automaten ist auch die Lösung von enumerativen Problemen, die keine rationalen erzeugenden Funktionen besitzen, möglich.
Peter Tittmann

11. Ausblicke

Zusammenfassung
Zum Abschluss möchten wir noch einige Methoden, Probleme und Anwendungen der enumerativen Kombinatorik aufzeigen, die in diesem Buch leider keinen Platz finden konnten. Dazu gehören eine Übersicht über algebraische Strukturen sowie Methoden aus verschiedenen Teilgebieten der Mathematik, die für die Kombinatorik besondere Bedeutung besitzen und Beispiele für schwierige offene Probleme der enumerativen Kombinatorik.
Peter Tittmann

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise