Einführung in die Kombinatorik (eBook)

lt;html>

Konrad Jacobs ist emeritierter Professor am mathematischen Institut der  Friedrich-Alexander-Universität Erlangen-Nürnberg.

Dieter Jungnickel ist Professor am Institut für Mathematik der Universität Augsburg.

Frontmatter 1
Inhaltsverzeichnis 9
I. Das kleine Einmaleins der Kombinatorik 13
II. Der Heiratssatz und seine Verwandten 35
III. Orthogonale lateinische Quadrate 74
IV. Der Satz vom Diktator 99
V. Fastperiodische 0-1-Folgen 108
VI. Der Satz von Ramsey 116
VII. Der Satz von van der Waerden 124
VIII. Codes 140
IX. Endliche projektive Ebenen und Räume 183
X. Blockpläne 221
XI. Symmetrische Blockpläne und Differenzmengen 253
XII. Partitionen 289
XIII. Die Abzähltheorie von Pólya 304
XIV. Kombinatorische Betrachtungen topologischen Ursprungs 326
XV. Spiele auf Graphen 350
XVI. Spezielle Folgen von ganzen Zahlen 362
Backmatter 381

lt;html>

"This book is an excellent introduction to a lot of aspects of combinatorial theory, and I enjoyed reading it very much."
Herman J. Tiersma in: Zentralblatt für Mathematik 103572004

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: