Kombinatorik

Gegenstand und zentrale Bereiche

Kombinatorik ist eine Teildisziplin der Mathematik. Sie untersucht endliche oder abzählbar unendliche diskrete Strukturen und wird deshalb der Diskreten Mathematik zugerechnet. Eine diskrete Struktur besteht aus einzelnen, unterscheidbaren Elementen und nicht aus einem kontinuierlichen Bereich.

Zu den Gegenständen gehören unter anderem Graphen, mit denen sich die Graphentheorie beschäftigt, sowie teilgeordnete Mengen wie Verbände, Matroide, kombinatorische Designs, lateinische Quadrate, Parkettierungen und Partitionen. Außerdem untersucht die Kombinatorik klassische Anordnungs- und Auswahlprobleme: Permutationen, Variationen und Kombinationen von Objekten. Die Abgrenzung zu anderen Teilgebieten der Diskreten Mathematik ist fließend.

Nach Gegenständen und Methoden werden verschiedene Teildisziplinen unterschieden: algebraische, analytische, geometrische, topologische und probabilistische Kombinatorik, kombinatorische Spieltheorie und Ramseytheorie. Die kombinatorische Optimierung befasst sich speziell mit der Optimierung diskreter Strukturen. Nach einer Definition von George Pólya untersucht die Kombinatorik das Abzählen, die Existenz und die Konstruktion von Konfigurationen.

Geschichte und Anwendungen

Die Bezeichnung „Kombinatorik“ geht auf Gottfried Wilhelm Leibniz zurück. In seiner Dissertatio de arte combinatoria aus dem Jahr 1666 beschäftigte er sich mit Permutationen. Historisch entwickelte sich die Kombinatorik aus Abzählproblemen diskreter Strukturen. Solche Probleme traten im 17. Jahrhundert insbesondere bei der Wahrscheinlichkeitsanalyse von Glücksspielen auf, etwa in Arbeiten von Blaise Pascal.

Der klassische Bereich des Abzählens wird als abzählende Kombinatorik bezeichnet. Wichtige Stichwörter sind Variationen und Kombinationen. Lange Zeit wurden für einzelne Probleme jeweils eigene, situationsbezogene Methoden entwickelt. Deshalb nahm die Kombinatorik in der Mathematik zunächst eine Außenseiterrolle ein. Zusammenfassende Theorien ihrer Teilgebiete entstanden erst im 20. Jahrhundert, beispielsweise in den Schulen von Gian-Carlo Rota und Richard P. Stanley.

Heute wird die Kombinatorik in zahlreichen Bereichen angewendet. Dazu gehören Geometrie, Wahrscheinlichkeitstheorie, Algebra, Mengenlehre und Topologie. In der Informatik spielt sie beispielsweise für die Kodierungstheorie eine Rolle. Weitere Anwendungen liegen in der theoretischen Physik, insbesondere in der statistischen Mechanik, sowie in der Unternehmensforschung, etwa bei Optimierungsproblemen und der Lagerhaltung.