Einführung in die Kombinatorik (eBook)

Dieter Jungnickel (Autor)

eBook Download: PDF

2008 | 1., 2. völlig neu bearb. und erw. Aufl. 2004
418 Seiten
De Gruyter (Verlag)
978-3-11-019799-0 (ISBN)

Infos

Ziel dieser vollständig überarbeiteten und erweiterten Neuauflage ist es, eine weitgehend elementare Einführung in ausgewählte Teile der Kombinatorik zu geben. Dabei wird stets versucht, nicht nur die Grundlagen darzustellen, sondern auch in jedem Kapitel exemplarisch einige tiefer liegende Resultate vollständig zu beweisen.

Highlights sind:

• allgemeine Lösung des Kirkmanschen Schulmädchenproblems und mehr über Blockpläne
• projektive Ebenen und Räume, einschließlich des Freundschaftstheorems
• Anwendungen in der Kryptographie, Authentikation von Nachrichten, Zugangskontrolle zu geheimen Informationen
• Heiratssatz und eine Fülle verwandter Sätze, etwa über Flüsse auf Netzwerken
• allgemeine Widerlegung der Eulerschen Vermutung über Paare orthogonaler lateinischer Quadrate
• der Satz vom Diktator
• verblüffende Eigenschaften der Morse-Thue-Folge
• einige Perlen aus der Codierungstheorie, inklusive konkreter Anwendungen etwa bei Prüfziffersystemen
• der klassische Satz von Ramsey und verwandte Ergebnisse
• Partitionen und Abzählen, etwa das klassische Menage-Problem
• Endliche Geometrie und Graphentheorie, insbesondere ein kurzer Beweis des Fünffarbensatzes und das Königsberger Brückenproblem

Das Buch wendet sich an Dozenten, die eine entsprechende Vorlesung über Kombinatorik halten, sowie an Studenten der Mathematik, denen das Buch als Begleitlektüre zu einer solchen Vorlesung oder zum Selbststudium dienen kann. Angesprochen sind auch Lehrer und Schüler in der gymnasialen Oberstufe, die im Rahmen eines Leistungskurses erste Einblicke in die reizvollen und teilweise sehr direkten Fragestellungen der Kombinatorik gewinnen wollen.

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.

Autor

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.

Inhalt

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

Rezensionen

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

Textauszug

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:

Produkt-Details

• Erscheint lt. Verlag: 22.8.2008
• Reihe/Serie: De Gruyter Lehrbuch
• Verlagsort: Berlin/Boston
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Technik
• Schlagworte: Kombinatorik
• ISBN-10: 3-11-019799-5 / 3110197995
• ISBN-13: 978-3-11-019799-0 / 9783110197990