Elementare Kombinatorik für die Informatik

Kurt-Ulrich Witt

Description

Das Buch enthält für Informatiker wichtige Grundlagen der diskreten Mathematik, insbesondere der Kombinatorik und zeigt an vielen Beispielen und Aufgaben deren Anwendungsmöglichkeiten auf

Das Buch ist auch zum Selbststudium gut geeignet: Jedes Kapitel beginnt mit Lernzielen, Marginalien enthalten die wichtigen Begriffe, über 40 Aufgaben mit Musterlösungen

Die Inhalte werden mathematisch präzise dargestellt, die Beschäftigung damit stärkt die Problemlösekompetenz?

Includes supplementary material: sn.pub/extras

Auf wie viele Arten und Weisen können die Elemente einer Menge einer anderen zugeordnet werden? Wie viele Möglichkeiten gibt es, aus einer Menge eine bestimmte Anzahl von Elementen auszuwählen? Wie können Summen berechnet werden? Wie können Rekursionsgleichungen aufgelöst werden? Das sind Fragestellungen, die in vielen Bereichen der Informatik gelöst werden müssen. Das Buch gibt eine Einführung in Konzepte, Methoden und Verfahren der Diskreten Mathematik, insbesondere der Kombinatorik, mit denen solche Fragestellungen behandelt werden können. Wegen seiner didaktischen Elemente wie Vorgabe von Lernzielen, Zusammenfassungen, Marginalien und einer Vielzahl von Übungen mit Musterlösungen eignet sich das Buch nicht nur als Begleitlektüre zu entsprechenden Informatik- und Mathematik-Lehrveranstaltungen, sondern insbesondere auch zum Selbststudium.​

Permutationen und Kombinationen.- Partitionen.- Abzählmethoden und das Urnenmodell.- Erzeugende Funktionen.- Lineare Differenzengleichungen.- Diskretes Differenzieren und Integrieren.- Anhang und Lösungen zu den Aufgaben.

Sujets

• Data Science
• Computer Science
• Computers
• Informatique
• Mathematics
• Discrete mathematics
• A

Informations

• Publié par: Springer Fachmedien Wiesbaden
• Date de parution: 19 mars 2013
• Nombre de lectures: 2
• EAN13: 9783658009946
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Kurt-Ulrich Witt
Elementare
Kombinatorik für
die Informatik
Abzählungen, Dif erenzengleichungen,
diskretes Dif erenzieren und IntegrierenElementareKombinatorikfürdieInformatikKurt-UlrichWitt
ElementareKombinatorik
fürdieInformatik
Abzählungen,Diferenzengleichungen,
diskretesDiferenzierenundIntegrierenKurt-UlrichWitt
HochschuleBonn-Rhein-Sieg
SanktAugustin,Deutschland
[e-mail]
ISBN978-3-658-00993-9
ISBN978-3-658-00994-6(eBook)
DOI10.1007/978-3-658-00994-6
DieDeutscheNationalbibliothekverzeichnetdiesePublikationinderDeutschenNationalbibliografie;detailliertebibliografischeDatensindimInternetüberhttp://dnb.d-nb.de abrufbar.
Springer
Vieweg
©SpringerFachmedienWiesbaden2013
DiesesWerkeinschließlichallerseinerTeileisturheberrechtlichgeschützt.JedeVerwertung,dienichtaus-
drücklichvomUrheberrechtsgesetzzugelassenist,bedarfdervorherigenZustimmungdesVerlags.Dasgilt
insbesonderefürVervielfältigungen,Bearbeitungen,Übersetzungen,MikroverfilmungenunddieEinspeicherungundVerarbeitunginelektronischenSystemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk
berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der
Warenzeichen- und Markenschutz-Gesetzgebungals frei zu betrachtenwären unddaher von jedermann
benutztwerdendürfen.
Planung und Lektorat:UlrikeSchmickler-Hirzebruch|BarbaraGerlach
GedrucktaufsäurefreiemundchlorfreigebleichtemPapier.
Springer Vieweg ist eine Marke von Springer DE. Springer DE ist Teil der Fachverlagsgruppe Springer
Science+BusinessMedia
www.springer-vieweg.deVorwort v
Vorwort
Kombinatorische Fragestellungen wie z.B. die Frage nach der Anzahl der
M¨oglichkeiten, sechs Zahlen aus 49 zu ziehen, oder die Frage danach, wie
viele M¨oglichkeiten es gibt, mit vier Wurfeln¨ eine bestimmte Augenzahl zu
werfen, tauchen nicht nur im alltaglichen Leben auf. Auch in vielen
Berei-¨
chenderInformatikentstehenAuswahl-undZuordnungsprobleme:Wievie-
leM¨oglichkeitengibtes,eineMengevonAuftr¨ageninTeilmengenbestimmter Gr¨oße aufzuteilen und Maschinen entsprechender Kapazit¨at
zuzuordnen? Wie viele Passw¨orter einer bestimmten L¨ange konnen¨ ub¨ er einem
gegebenen Alphabet gebildet werden, wobei nicht alle Zeichenkombinationen
erlaubtsind?WievieleSchrittebenotigteinSortierverfahren,umeineMen-¨
ge von Datens¨atzen aufsteigend zu sortieren? Auf wie viele Arten kann eine
Menge von Daten in eine Zugriffsstruktur eingeordnet werden? Oft lassen
sich diese Anzahlen relativ leicht mithilfe von Rekursionsgleichungen oder
Summenbeschreiben.AndiesenimplizitenDarstellungenkannaberzumeist
nicht unmittelbar die tatsachliche Anzahl abgelesen werden. So stellt sich¨
die Frage danach, ob es Verfahren gibt, mit denen Rekursionsgleichungen
und Summen in Formeln transformiert werden k¨onnen, welche die direkte
Berechnung der Anzahlen erlauben. In diesem Buch werden grundlegende
Konzepte, Methoden und Verfahren fur¨ die Losung¨ solcher Probleme
vorgestellt.
DasBuchrichtetsichanBachelor-StudierendeinInformatik-Studiengangen¨
jeglicher Ausrichtung sowie an Bac der Mathematik im
Haupt-oderNebenfach.EsistalsBegleitlekture¨
zuentsprechendenLehrveranstaltungenanHochschulenallerArtundinsbesonderezumSelbststudium
geeignet. Jedes Kapitel beginnt mit einer seinen Inhalt motivierenden
Einleitung und der Auflistung von Lernzielen, die durch das Studium des
Kapitels erreicht werden sollen. Zusammenfassungen am Ende von Abschnitten
oder am Ende von Kapiteln bieten Gelegenheit, den Stoff zu reflektieren.
DiemeistenBeweisesindvergleichsweiseausfuhrlic¨ hundmitQuerverweisen
versehen, die die Zusammenhange aufzeigen.¨
Eingestreut sind ub¨ er funfzig¨ Aufgaben, deren Bearbeitung zur Festigung
¨des Wissens und zum Uben der dargestellten Methoden und Verfahren
dienen. Zu fast allen Aufgaben sind am Ende des Buches oder im Text
Musterlosungen aufgefuhrt. Die Aufgaben und Losungen sind als integraler¨ ¨ ¨
Bestandteil des Buches konzipiert. Wichtige Begriffe sind als Marginalien
aufgefuhrt;¨ der Platz zwischen den Marginalien bietet Raum fur¨ eigene
Notizen.
Ich bedanke mich herzlich bei: den Autoren der im Literaturverzeichnis
aufgefuhrtenWerke,dieichfurdeneinenoderanderenAspektverwendethabe,¨ ¨
ich empfehle sie allesamt fur¨ weitere erg¨anzende Studien; bei den
Studierenden, die meine Lehrveranstaltungen zu Themen dieses Buches besucht und
die durch kritische Anmerkungen und hilfreiche Vorschl¨age wesentlich zurvi Vorwort
Verbesserung der Darstellungen beigetragen haben; bei Frau
SchmicklerHirzebruch vom Springer-Verlag dafur,¨ dass sie mich zum Schreiben dieses
Buches ermuntert und geduldig begleitet hat; und bei meiner Familie fur¨
die Gewahrung des zeitlichen Freiraumes, in Ruhe an dem Buch arbeiten¨
zu k¨onnen.
Bedburg, im Januar 2013
K.-U. WittInhaltsverzeichnis vii
Inhaltsverzeichnis
Einleitung 1
1 Permutationen und Kombinationen 3
1.1 Permutationen . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Permutationen ohne Wiederholung . . . . . . . . . . 4
1.1.2 Stirlingzahlen erster Art . . . . . . . . . . . . . . . . 7
1.1.3 Typ einer Permutation . . . . . . . . . . . . . . . . . 11
1.1.4 Permutationen mit Wiederholung . . . . . . . . . . . 13
1.1.5 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 14
1.2 Kombinationen . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.1 Kombinationen ohne Wiederholung . . . . . . . . . . 15
1.2.2 Kom mit . . . . . . . . . . . 16
1.2.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 18
1.3 Multinomialkoeffizienten . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Binomialkoeffizienten . . . . . . . . . . . . . . . . . . 19
1.3.2 Multinomialkoeffizienten . . . . . . . . . . . . . . . . 27
1.3.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 32
2 Partitionen 33
2.1 Zahlpartitionen . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1.1 Geordnete Zahlpartitionen . . . . . . . . . . . . . . . 34
2.1.2 Ungeordnete Zahlpartitionen . . . . . . . . . . . . . . 35
2.1.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 37
2.2 Mengenpartitionen . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.1 Stirlingzahlen zweiter Art . . . . . . . . . . . . . . . 38
2.2.2 Anzahl von Abbildungen . . . . . . . . . . . . . . . . 40
2.2.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 46
2.3 Catalanzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3 Abzahlmethoden und das Urnenmodell 49¨
3.1 Elementare Abzahlmethoden . . . . . . . . . . . . . . . . . . 49¨
3.1.1 Summenregel . . . . . . . . . . . . . . . . . . . . . . 49
3.1.2 Gleichheitsregel . . . . . . . . . . . . . . . . . . . . . 50
3.1.3 Produktregel . . . . . . . . . . . . . . . . . . . . . . 50
3.1.4 Doppeltes Abzahlen . . . . . . . . . . . . . . . . . . 51¨
3.1.5 Das Schubfachprinzip . . . . . . . . . . . . . . . . . . 52
3.1.6 Das Prinzip der Inklusion und Exklusion . . . . . . . 53
3.1.7 Zusammenfassung . . . . . . . . . . . . . . . . . . . . 55
3.2 Das Urnenmodell . . . . . . . . . . . . . . . . . . . . . . . . 56
4 Erzeugende Funktionen 59
4.1 Definitionen und grundlegende Eigenschaften . . . . . . . . . 59
4.2 Erzeugende Funktionen fur¨ Kombinationen . . . . . . . . . . 64viii Inhaltsverzeichnis
4.3 Erzeugende Funktionen fur¨ Permutationen . . . . . . . . . . 68
4.4 Weitere Anwendungen und Zusammenfassung . . . . . . . . 70
5 Lineare Differenzengleichungen 79
5.1 Definitionen und Beispiele . . . . . . . . . . . . . . . . . . . 80
5.2 Allgemeine Eigenschaften von L¨osungen . . . . . . . . . . . 81
5.3 Losungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . 84¨
5.3.1 Losungsverfahren fur homogene Differenzengleichungen 84¨ ¨
5.3.2 L¨fur¨
inhomogeneDifferenzengleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.4 L¨osung homogener linearer Differenzengleichungen zweiten
Grades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.5 Losung mithilfe von erzeugenden Funktionen . . . . . . . . . 110¨
5.5.1 Gleichungen zweiten Grades . . . . . . . . . . . . . . 111
5.5.2 Gleich ersten Grades . . . . . . . . . . . . . . . 118
5.5.3 Gleichungen h¨oheren Grades . . . . . . . . . . . . . . 119
5.6 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . 124
6 Diskretes Differenzieren und Integrieren 125
6.1 Diskrete Mengen und Funktionen . . . . . . . . . . . . . . . 125
6.2 Differenzenoperatoren und diskrete Ableitungen . . . . . . . 128
6.3 Polynomdarstellung diskreter Funktionen . . . . . . . . . . . 137
6.4 Diskrete Stammfunktionen und Summation . . . . . . . . . 140
6.4.1 Definitionen und elementare Eigenschaften . . . . . . 140
6.4.2 Berechnung von Summen durch diskrete Integration . 142
6.4.3 Berechnung von durch partielle diskrete
Integration . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.5 Weitere Summationsmethoden . . . . . . . . . . . . . . . . . 149
6.6 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . 153
A Anhang 155
A.1 Zahlenmengen . . . . . . . . . . . . . . . . . . . . . . . . . . 155
A.2 Relationen und Funktionen . . . . . . . . . . . . . . . . . . . 155
A.3 Spezielle Funktionen, Summen und Produkte . . . . . . . . . 157
L¨osungen zu den Aufgaben 161
Literatur 197
Stichwortverzeichnis 199Einleitung 1
Einleitung
¨Kombinatorische Uberlegungen kennen wir aus dem taglichen Leben:
Wie¨
vieleM¨oglichkeitengibtes,sechsZahlenaus49zuziehen?WievieleM¨oglich-
keitengibtes,eineAnzahlvonPersonenaneinerAnzahlvonTischengewisserGr¨oßezuplatzieren?WieoftklingenGl¨aser,wennnPersonenanstoßen?
Im Kern geht es um die Frage, wie viele Moglichkeiten es gibt, aus einer¨
endlichen Menge Teilmengen einer bestimmten Große auszuwahlen. Dabei¨ ¨
ist es von Bedeutung, ob bei der Auswahl der Elemente die Reihenfolge
der Auswahl eine Rolle spielt oder ob Elemente mehrfach oder nur einmal
ausgew¨ahlt werden konnen.¨ Auch in der Informatik ist es oft erforderlich,
¨kombinatorische Uberlegungen anzustellen: Wie viele Verbindungen einer
bestimmten Lange gibt es in einem Rechnernetz? Wie viel