Kombinatorik

Die Kombinatorik ist ein Teilgebiet der Mathematik, das sich in erster Linie mit dem Zählen als Mittel und Zweck zur Gewinnung von Ergebnissen sowie mit bestimmten Eigenschaften endlicher Strukturen befasst. Sie steht in engem Zusammenhang mit vielen anderen Bereichen der Mathematik und hat zahlreiche Anwendungen, die von der Logik bis zur statistischen Physik und von der Evolutionsbiologie bis zur Computerwissenschaft reichen. ⓘ

Über den vollen Umfang der Kombinatorik herrscht keine allgemeine Übereinstimmung. Laut H.J. Ryser ist eine Definition des Themas schwierig, weil es so viele mathematische Teilgebiete umfasst. Soweit ein Gebiet durch die Art der Probleme, die es behandelt, beschrieben werden kann, befasst sich die Kombinatorik mit:

der Aufzählung (Zählung) bestimmter Strukturen, die manchmal als Anordnungen oder Konfigurationen in einem sehr allgemeinen Sinne bezeichnet werden und mit endlichen Systemen verbunden sind,
das Vorhandensein solcher Strukturen, die bestimmte vorgegebene Kriterien erfüllen,
die Konstruktion dieser Strukturen, möglicherweise auf verschiedene Weise, und
Optimierung: die Suche nach der "besten" Struktur oder Lösung unter mehreren Möglichkeiten, sei es die "größte", die "kleinste" oder eine andere, die ein Optimalitätskriterium erfüllt. ⓘ

Leon Mirsky hat gesagt: "Die Kombinatorik ist eine Reihe miteinander verbundener Studien, die etwas gemeinsam haben und doch in ihren Zielen, ihren Methoden und dem Grad der Kohärenz, den sie erreicht haben, stark voneinander abweichen." Eine Möglichkeit, die Kombinatorik zu definieren, besteht vielleicht darin, ihre Unterabteilungen mit ihren Problemen und Techniken zu beschreiben. Dies ist der Ansatz, der im Folgenden verwendet wird. Es gibt jedoch auch rein historische Gründe für die Einbeziehung oder Nicht-Einbeziehung einiger Themen in die Kombinatorik. Obwohl sie sich in erster Linie mit endlichen Systemen befasst, können einige kombinatorische Fragen und Techniken auf einen unendlichen (insbesondere abzählbaren), aber diskreten Rahmen ausgedehnt werden. ⓘ

Die Kombinatorik ist bekannt für die Breite der Probleme, mit denen sie sich befasst. Kombinatorische Probleme tauchen in vielen Bereichen der reinen Mathematik auf, insbesondere in der Algebra, der Wahrscheinlichkeitstheorie, der Topologie und der Geometrie, aber auch in vielen Anwendungsbereichen. Viele kombinatorische Fragen wurden in der Vergangenheit isoliert betrachtet, indem man eine Ad-hoc-Lösung für ein Problem fand, das in irgendeinem mathematischen Kontext auftrat. Im späten zwanzigsten Jahrhundert wurden jedoch leistungsfähige und allgemeine theoretische Methoden entwickelt, die die Kombinatorik zu einem eigenständigen Zweig der Mathematik machten. Einer der ältesten und am leichtesten zugänglichen Teile der Kombinatorik ist die Graphentheorie, die ihrerseits zahlreiche natürliche Verbindungen zu anderen Bereichen aufweist. In der Informatik wird die Kombinatorik häufig eingesetzt, um Formeln und Schätzungen bei der Analyse von Algorithmen zu erhalten. ⓘ

Ein Mathematiker, der sich mit Kombinatorik beschäftigt, wird als Kombinatoriker. ⓘ

Die Kombinatorik ist eine Teildisziplin der Mathematik, die sich mit endlichen oder abzählbar unendlichen diskreten Strukturen beschäftigt und deshalb auch dem Oberbegriff diskrete Mathematik zugerechnet wird. Beispiele sind Graphen (Graphentheorie), teilgeordnete Mengen wie Verbände, Matroide, kombinatorische Designs, lateinische Quadrate, Parkettierungen, Permutationen von Objekten, Partitionen. Die Abgrenzung zu anderen Teilgebieten der diskreten Mathematik ist fließend. Eine Definition von George Pólya bezeichnet die Kombinatorik als Untersuchung des Abzählens, der Existenz und Konstruktion von Konfigurationen. ⓘ

Je nach den verwendeten Methoden und Gegenständen unterscheidet man auch Teildisziplinen wie algebraische Kombinatorik, analytische Kombinatorik, geometrische und topologische Kombinatorik, probabilistische Kombinatorik, Kombinatorische Spieltheorie, Ramseytheorie. Speziell mit der Optimierung diskreter Strukturen beschäftigt sich die kombinatorische Optimierung. ⓘ

Geschichte

Ein Beispiel für ein Wechselgeläut (mit sechs Glocken), eines der frühesten nichttrivialen Ergebnisse der Graphentheorie. ⓘ

Grundlegende kombinatorische Konzepte und Aufzählungsergebnisse tauchten bereits in der Antike auf. Im 6. Jahrhundert v. Chr. behauptet der altindische Arzt Sushruta in der Sushruta Samhita, dass 63 Kombinationen aus 6 verschiedenen Geschmäckern gebildet werden können, wobei jeweils ein Geschmack, zwei Geschmäcker usw. genommen werden, so dass alle 2⁶ - 1 Möglichkeiten berechnet werden können. Der griechische Historiker Plutarch berichtet über einen Streit zwischen Chrysippus (3. Jh. v. Chr.) und Hipparchus (2. Jh. v. Chr.) über ein ziemlich heikles Aufzählungsproblem, von dem später gezeigt wurde, dass es mit den Schröder-Hipparchus-Zahlen zusammenhängt. Schon früher, im Ostomachion, hat Archimedes (3. Jh. v. Chr.) möglicherweise die Anzahl der Konfigurationen eines Kachelpuzzles betrachtet, während kombinatorische Interessen möglicherweise in verlorenen Werken von Apollonius vorhanden waren. ⓘ

Im Mittelalter wurde die Kombinatorik weiter erforscht, allerdings weitgehend außerhalb der europäischen Zivilisation. Der indische Mathematiker Mahāvīra (um 850) stellte Formeln für die Anzahl der Permutationen und Kombinationen auf, die indischen Mathematikern möglicherweise schon im 6. Der Philosoph und Astronom Rabbi Abraham ibn Esra (um 1140) stellte die Symmetrie der Binomialkoeffizienten fest, während eine geschlossene Formel später von dem Talmudisten und Mathematiker Levi ben Gerson (besser bekannt als Gersonides) im Jahr 1321 aufgestellt wurde. Das arithmetische Dreieck - ein grafisches Diagramm, das die Beziehungen zwischen den binomischen Koeffizienten aufzeigt - wurde von Mathematikern in Abhandlungen aus dem 10. Später, im mittelalterlichen England, lieferte die Campanologie Beispiele für das, was heute als Hamiltonsche Zyklen in bestimmten Cayley-Graphen über Permutationen bekannt ist. ⓘ

Während der Renaissance erlebte die Kombinatorik zusammen mit der übrigen Mathematik und den Naturwissenschaften eine Wiedergeburt. Die Arbeiten von Pascal, Newton, Jacob Bernoulli und Euler wurden für das entstehende Gebiet grundlegend. In der Neuzeit trugen die Arbeiten von J.J. Sylvester (Ende des 19. Jahrhunderts) und Percy MacMahon (Anfang des 20. Jahrhunderts) dazu bei, die Grundlage für die enumerative und algebraische Kombinatorik zu legen. Auch die Graphentheorie erfreute sich zur gleichen Zeit eines wachsenden Interesses, insbesondere im Zusammenhang mit dem Vier-Farben-Problem. ⓘ

In der zweiten Hälfte des 20. Jahrhunderts erlebte die Kombinatorik einen rasanten Aufschwung, der zur Gründung Dutzender neuer Zeitschriften und Konferenzen zu diesem Thema führte. Zum Teil wurde dieses Wachstum durch neue Verbindungen und Anwendungen auf anderen Gebieten, von der Algebra bis zur Wahrscheinlichkeitsrechnung, von der Funktionalanalysis bis zur Zahlentheorie usw., vorangetrieben. Diese Verbindungen ließen die Grenzen zwischen der Kombinatorik und Teilen der Mathematik und der theoretischen Informatik verschwinden, führten aber gleichzeitig zu einer teilweisen Zersplitterung des Fachs. ⓘ

Ansätze und Teilgebiete der Kombinatorik

Enumerative Kombinatorik

Fünf binäre Bäume auf drei Scheitelpunkten, ein Beispiel für katalanische Zahlen. ⓘ

Die enumerative Kombinatorik ist das klassischste Gebiet der Kombinatorik und konzentriert sich auf das Zählen der Anzahl bestimmter kombinatorischer Objekte. Obwohl das Zählen der Anzahl von Elementen in einer Menge ein recht weit gefasstes mathematisches Problem ist, lassen sich viele der Probleme, die in Anwendungen auftreten, relativ einfach kombinatorisch beschreiben. Die Fibonacci-Zahlen sind das grundlegende Beispiel für ein Problem der enumerativen Kombinatorik. Die Zwölffachmethode bietet einen einheitlichen Rahmen für das Zählen von Permutationen, Kombinationen und Partitionen. ⓘ

Analytische Kombinatorik

Die analytische Kombinatorik befasst sich mit der Aufzählung von kombinatorischen Strukturen unter Verwendung von Werkzeugen aus der komplexen Analyse und der Wahrscheinlichkeitstheorie. Im Gegensatz zur enumerativen Kombinatorik, die explizite kombinatorische Formeln und erzeugende Funktionen zur Beschreibung der Ergebnisse verwendet, zielt die analytische Kombinatorik darauf ab, asymptotische Formeln zu erhalten. ⓘ

Partitionstheorie

Eine ebene Partition. ⓘ

Die Partitionstheorie untersucht verschiedene Aufzählungs- und asymptotische Probleme im Zusammenhang mit ganzzahligen Partitionen und steht in engem Zusammenhang mit q-Serien, speziellen Funktionen und orthogonalen Polynomen. Ursprünglich ein Teil der Zahlentheorie und Analysis, wird sie heute als Teil der Kombinatorik oder als eigenständiges Gebiet betrachtet. Sie umfasst den bijektiven Ansatz und verschiedene Werkzeuge der Analysis und analytischen Zahlentheorie und hat Verbindungen zur statistischen Mechanik. ⓘ

Graphentheorie

Petersen-Graph. ⓘ

Graphen sind grundlegende Objekte der Kombinatorik. Die Betrachtungen der Graphentheorie reichen von der Aufzählung (z. B. die Anzahl der Graphen auf n Scheitelpunkten mit k Kanten) über bestehende Strukturen (z. B. Hamiltonsche Zyklen) bis hin zu algebraischen Darstellungen (z. B. hat das Tutte-Polynom TG(x,y) bei einem Graphen G und zwei Zahlen x und y eine kombinatorische Interpretation?) Obwohl es sehr enge Verbindun_gen zwischen Graphentheorie und Kombinatorik gibt, werden sie manchmal als getrennte Fächer betrachtet. Obwohl die Methoden der Kombinatorik auf viele Probleme der Graphentheorie anwendbar sind, werden die beiden Disziplinen im Allgemeinen dazu verwendet, Lösungen für unterschiedliche Arten von Problemen zu finden. ⓘ

Entwurfstheorie

Die Entwurfstheorie befasst sich mit kombinatorischen Entwürfen, d. h. mit Sammlungen von Teilmengen mit bestimmten Schnittmengeneigenschaften. Blockentwürfe sind kombinatorische Entwürfe eines speziellen Typs. Dieser Bereich ist einer der ältesten Teile der Kombinatorik, wie z. B. das Schulmädchenproblem von Kirkman aus dem Jahr 1850 zeigt. Die Lösung dieses Problems ist ein Spezialfall eines Steiner-Systems, das eine wichtige Rolle bei der Klassifizierung endlicher einfacher Gruppen spielt. Das Gebiet hat weitere Verbindungen zur Kodierungstheorie und zur geometrischen Kombinatorik. ⓘ

Endliche Geometrie

Die endliche Geometrie befasst sich mit geometrischen Systemen, die nur eine endliche Anzahl von Punkten haben. Untersucht werden vor allem Strukturen, die denen der kontinuierlichen Geometrie (euklidische Ebene, reeller projektiver Raum usw.) entsprechen, aber kombinatorisch definiert sind. Dieser Bereich bietet eine reiche Quelle von Beispielen für die Entwurfstheorie. Es ist nicht mit der diskreten Geometrie (kombinatorische Geometrie) zu verwechseln. ⓘ

Ordnungstheorie

Hasse-Diagramm der Potenzmenge von {x,y,z}, geordnet durch Einschluss. ⓘ

Die Ordnungstheorie ist die Lehre von partiell geordneten Mengen, sowohl endlichen als auch unendlichen. Verschiedene Beispiele für partielle Ordnungen tauchen in der Algebra, Geometrie, Zahlentheorie und in der gesamten Kombinatorik und Graphentheorie auf. Zu den bemerkenswerten Klassen und Beispielen für partielle Ordnungen gehören Gitter und boolesche Algebren. ⓘ

Matroidentheorie

Die Matroidentheorie abstrahiert einen Teil der Geometrie. Sie untersucht die Eigenschaften von Mengen (in der Regel endliche Mengen) von Vektoren in einem Vektorraum, die nicht von den einzelnen Koeffizienten in einer linearen Abhängigkeitsbeziehung abhängen. Zur Matroidentheorie gehören nicht nur die Struktur, sondern auch aufzählende Eigenschaften. Die Matroidentheorie wurde von Hassler Whitney eingeführt und als Teil der Ordnungstheorie untersucht. Heute ist sie ein eigenständiges Forschungsgebiet mit einer Reihe von Verbindungen zu anderen Teilen der Kombinatorik. ⓘ

Extremwert-Kombinatorik

Die Extremwertkombinatorik untersucht extreme Fragen zu Mengensystemen. In diesem Fall geht es um Fragen nach dem größtmöglichen Graphen, der bestimmte Eigenschaften erfüllt. Zum Beispiel ist der größte dreieckfreie Graph mit 2n Scheitelpunkten ein vollständiger zweistufiger Graph K_n,n. Oft ist es sogar zu schwierig, die extreme Antwort f(n) genau zu finden, und man kann nur eine asymptotische Schätzung abgeben. ⓘ

Die Ramsey-Theorie ist ein weiterer Teil der extremalen Kombinatorik. Sie besagt, dass jede ausreichend große Konfiguration eine Art von Ordnung enthält. Sie ist eine fortgeschrittene Verallgemeinerung des Taubenlochprinzips. ⓘ

Probabilistische Kombinatorik

Selbstvermeidende Wanderung in einem quadratischen Gittergraphen. ⓘ

In der probabilistischen Kombinatorik geht es um folgende Fragen: Wie hoch ist die Wahrscheinlichkeit einer bestimmten Eigenschaft für ein zufälliges diskretes Objekt, z. B. einen Zufallsgraphen? Wie groß ist zum Beispiel die durchschnittliche Anzahl der Dreiecke in einem Zufallsgraphen? Probabilistische Methoden werden auch verwendet, um die Existenz von kombinatorischen Objekten mit bestimmten vorgeschriebenen Eigenschaften zu bestimmen (für die explizite Beispiele schwer zu finden sein könnten), indem einfach beobachtet wird, dass die Wahrscheinlichkeit, ein Objekt mit diesen Eigenschaften zufällig auszuwählen, größer als 0 ist. Dieser Ansatz (oft als probabilistische Methode bezeichnet) hat sich bei Anwendungen in der extremen Kombinatorik und der Graphentheorie als sehr effektiv erwiesen. Ein eng verwandtes Gebiet ist die Untersuchung endlicher Markov-Ketten, insbesondere bei kombinatorischen Objekten. Auch hier werden probabilistische Methoden verwendet, um die Mischzeit zu schätzen. ⓘ

Die probabilistische Kombinatorik, die oft mit Paul Erdős in Verbindung gebracht wird, der Pionierarbeit auf diesem Gebiet geleistet hat, wurde traditionell als eine Reihe von Werkzeugen zur Untersuchung von Problemen in anderen Bereichen der Kombinatorik betrachtet. Mit der Zunahme von Anwendungen zur Analyse von Algorithmen in der Informatik sowie der klassischen Wahrscheinlichkeitsrechnung, der additiven Zahlentheorie und der probabilistischen Zahlentheorie ist das Gebiet jedoch in letzter Zeit zu einem eigenständigen Bereich der Kombinatorik geworden. ⓘ

Algebraische Kombinatorik

Young-Diagramm einer Partition (5,4,1). ⓘ

Die algebraische Kombinatorik ist ein Bereich der Mathematik, der Methoden der abstrakten Algebra, insbesondere der Gruppentheorie und der Darstellungstheorie, in verschiedenen kombinatorischen Zusammenhängen einsetzt und umgekehrt kombinatorische Techniken auf Probleme der Algebra anwendet. Die algebraische Kombinatorik erweitert ständig ihren Umfang, sowohl in Bezug auf die Themen als auch auf die Techniken, und kann als der Bereich der Mathematik angesehen werden, in dem die Interaktion zwischen kombinatorischen und algebraischen Methoden besonders stark und bedeutend ist. ⓘ

Kombinatorik der Wörter

Konstruktion eines unendlichen Thue-Morse-Wortes. ⓘ

Die Wortkombinatorik beschäftigt sich mit formalen Sprachen. Sie entstand unabhängig voneinander in verschiedenen Bereichen der Mathematik, darunter Zahlentheorie, Gruppentheorie und Wahrscheinlichkeitsrechnung. Sie hat Anwendungen in der enumerativen Kombinatorik, der Fraktalanalyse, der theoretischen Informatik, der Automatentheorie und der Linguistik. Während viele Anwendungen neu sind, ist die klassische Chomsky-Schützenberger-Hierarchie von Klassen formaler Grammatiken vielleicht das bekannteste Ergebnis auf diesem Gebiet. ⓘ

Geometrische Kombinatorik

Ein Ikosaeder. ⓘ

Die geometrische Kombinatorik ist mit der konvexen und diskreten Geometrie verwandt, insbesondere mit der polyedrischen Kombinatorik. Sie fragt zum Beispiel, wie viele Flächen jeder Dimension ein konvexes Polytop haben kann. Metrische Eigenschaften von Polytopen spielen ebenfalls eine wichtige Rolle, z. B. der Satz von Cauchy über die Starrheit von konvexen Polytopen. Es werden auch spezielle Polytope betrachtet, wie Permutoeder, Assoziaeder und Birkhoff-Polytope. Kombinatorische Geometrie ist eine historische Bezeichnung für diskrete Geometrie. ⓘ

Topologische Kombinatorik

Aufspaltung einer Kette mit zwei Schnitten. ⓘ

Kombinatorische Analogien von Konzepten und Methoden der Topologie werden zur Untersuchung von Graphenfärbung, gerechter Teilung, Partitionen, teilweise geordneten Mengen, Entscheidungsbäumen, Halskettenproblemen und diskreter Morse-Theorie verwendet. Sie sollte nicht mit der kombinatorischen Topologie verwechselt werden, die eine ältere Bezeichnung für die algebraische Topologie ist. ⓘ

Arithmetische Kombinatorik

Die arithmetische Kombinatorik ist aus dem Zusammenspiel von Zahlentheorie, Kombinatorik, Ergodentheorie und harmonischer Analyse entstanden. Sie befasst sich mit kombinatorischen Schätzungen im Zusammenhang mit arithmetischen Operationen (Addition, Subtraktion, Multiplikation und Division). Die additive Zahlentheorie (manchmal auch additive Kombinatorik genannt) bezieht sich auf den Spezialfall, dass nur die Operationen Addition und Subtraktion beteiligt sind. Eine wichtige Technik in der arithmetischen Kombinatorik ist die Ergodentheorie dynamischer Systeme. ⓘ

Infinitäre Kombinatorik

Die unendliche Kombinatorik oder kombinatorische Mengenlehre ist eine Erweiterung der Ideen der Kombinatorik auf unendliche Mengen. Sie ist Teil der Mengentheorie, einem Bereich der mathematischen Logik, verwendet aber Werkzeuge und Ideen sowohl aus der Mengentheorie als auch aus der extremen Kombinatorik. ⓘ

Gian-Carlo Rota verwendete den Namen kontinuierliche Kombinatorik, um die geometrische Wahrscheinlichkeit zu beschreiben, da es viele Analogien zwischen Zählen und Messen gibt. ⓘ

Geschichte und Anwendung

Die Bezeichnung Kombinatorik geht auf Leibniz zurück. In seiner "Dissertatio de arte combinatoria" aus dem Jahr 1666 beschäftigte er sich mit Permutationen. Historisch entstand die Kombinatorik aus Abzählproblemen von diskreten Strukturen, wie sie im 17. Jahrhundert bei der Wahrscheinlichkeitsanalyse von Glücksspielen, etwa durch Blaise Pascal, auftraten. Dieser klassische Bereich der Kombinatorik wird zusammenfassend als abzählende Kombinatorik (Stichwörter: Variationen und Kombinationen) bezeichnet. Kennzeichnend für die in der abzählenden Kombinatorik auftretenden Probleme war, dass meist für jedes Einzelproblem ad hoc neue Methoden ersonnen werden mussten. Lange Zeit spielte die Kombinatorik deshalb eine Außenseiterrolle in der Mathematik, zusammenfassende Theorien ihrer Teilgebiete entstanden erst im 20. Jahrhundert, beispielsweise in den Schulen von Gian-Carlo Rota und Richard P. Stanley. ⓘ

Die Kombinatorik hat zahlreiche Anwendungen in anderen Gebieten der Mathematik wie Geometrie, Wahrscheinlichkeitstheorie, Algebra, Mengenlehre und Topologie, in der Informatik (zum Beispiel Kodierungstheorie) und der theoretischen Physik, insbesondere in der statistischen Mechanik sowie in der Unternehmensforschung (zum Beispiel Optimierung, Lagerhaltung). ⓘ