Kombinatorik
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.[1]
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 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.[2] 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).
Siehe auch
Literatur
- Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4.
- Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. 2. Auflage. de Gruyter, Berlin, New York 2004, ISBN 3-11-016727-1.
- Ronald Graham, Martin Grötschel, László Lovász (Herausgeber): Handbook of combinatorics, 2 Bände, Elsevier/North Holland und MIT Press 1995
- Jacobus van Lint, Richard M. Wilson: A Course in Combinatorics, Cambridge University Press, 2. Auflage 2001
- Claude Berge: Principles of Combinatorics, Academic Press 1971
- Alan Tucker: Applied combinatorics, Wiley, 3. Auflage 1995
- Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise, Springer 2002
- V.N. Sachkov: combinatorial analysis. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).
Weblinks
- Andreas Brinken: Einführung in die Kombinatorik – Schulmaterialien zum Thema Kombinatorik (PDF; 444 kB)
- Anders Björner, Richard P. Stanley: A combinatorial miscellany (PDF; 838 kB)
Einzelnachweise
- George Pólya, Robert Tarjan, Donald R. Woods: Notes on introductory combinatorics, Birkhäuser 1983, Vorwort
- Schülerduden: Die Mathematik II, Mannheim/Leipzig/Wien/Zürich: Dudenverklag, ISBN 3-411-04273-7