Einführung in die Kombinatorik

I Das kleine Einmaleins der Kombinatorik (S. 1-2)

In diesem einführenden Kapitel wollen wir einige elementare Aussagen und Prinzipien der klassischen Kombinatorik kennenlernen. Nach einem kurzen Rückblick auf die wichtigsten Begriffe der Mengenlehre (der auch dazu dient, die von uns verwendete Notation festzulegen) stellen wir drei grundlegende Abzählprinzipien vor und leiten dann die einfachsten Anzahlaussagen für endliche Mengen her, danach betrachten wir mit dem Inklusions-Exklusions-Prinzip ein etwas schwierigeres Abzählverfahren, das von fundamentaler Bedeutung ist. Hier können wir dann bereits etliche anspruchsvollere Anwendungen behandeln.

1 Mengen

Die Kombinatorik beschäftigt sich überwiegend mit endlichen Mengen. Das Unendliche kommt aber sogleich ebenfalls in die Kombinatorik hinein, weil sie Sätze zu beweisen sucht, die für Mengen ohne Beschränkung der Mächtigkeit (also der Anzahl ihrer Elemente) gelten. Ferner bedient sich die Kombinatorik manchmal analytischer, topologischer oder stochastischer Methoden, wodurch sie es mit den reellen und den komplexen Zahlen oder auch mit topologischen Räumen zu tun bekommt, dieser Fall tritt besonders dann ein, wenn man sogenannte asymptotische Aussagen beweisen will. Schließlich lassen sich manche Fragestellungen und Ergebnisse der Kombinatorik von endlichen auf unendliche Mengen übertragen. In diesem Buch steht die Kombinatorik der endlichen Mengen im Vordergrund. Wo dieser Rahmen überschritten wird, werden wir die benötigten Hilfsmittel per Zitat ausdrücklich, aber ohne Beweis bereitstellen. Aber auch beim Umgang mit endlichen Mengen werden wir uns Resultate aus anderen Gebieten der Mathematik, insbesondere aus der Linearen Algebra, der Algebra der endlichen Körper und der Theorie der endlichen Gruppen – wieder per Zitat ohne Beweis – zu Nutze machen. Wir setzen voraus, daß der Leser über gewisse Grundkenntnisse aus der naiven Mengenlehre, d. h. über Mengen und Abbildungen, verfügt. Es geht also nur noch darum, an gewisse Begriffsbildungen aus dieser Theorie zu erinnern und Bezeichnungen festzulegen. Die gesamte Kombinatorik ist, wie praktisch jeder Zweig der Mathematik, mit Hilfe der Begriffe " Menge" und " Abbildung" formulierbar.

Die weiteren Abschnitte dieses Kapitels haben auch den Zweck, dies an einfa chen Beispielen zu demonstrieren, dadurch soll insbesondere klar werden, daß zum Verständnis der Kombinatorik kein kombinatorischer Sonderverstand erforderlich ist. Dennoch werden wir später die konsequente Formulierung kombinatorischer Aussagen rein mit Hilfe der Begriffe " Menge" und " Abbildung" oft nicht voll durchführen, nämlich dann, wenn eine andere – beispielsweise verbale –Ausdrucksweise nach unserer Meinung besser geeignet ist, das Gemeinte klarzumachen.Von einem gewissen Stadium der Beschäftigung mit der Kombinatorik an sollte der Leser im Stande sein, mengentheoretischen Klartext selbstständig herzustellen, falls er dies wünscht. Folgende Mengen werden uns besonders beschäftigen: