www.wikidata.de-de.nina.az

Abzählende Kombinatorik Die abzählende Kombinatorik ist ein Teilbereich der Kombinatorik Sie beschäftigt sich mit der Be

Abzählende Kombinatorik

Die abzählende Kombinatorik ist ein Teilbereich der Kombinatorik. Sie beschäftigt sich mit der Bestimmung der Anzahl möglicher Anordnungen oder Auswahlen

  • unterscheidbarer oder nicht unterscheidbarer Objekte (d. h. „ohne“ bzw. „mit“ Wiederholung derselben Objekte) sowie
  • mit oder ohne Beachtung ihrer Reihenfolge (d. h. „geordnet“ bzw. „ungeordnet“).
Zahl der Variationen und Kombinationen von 10 Elementen zur k-ten Klasse und der partiellen Derangements (fixpunktfreie Permutationen) von 10 Elementen.
P*(10;k) k-Permutationen oder Variationen mit Wiederholung
P(10;k) k-Permutationen oder Variationen ohne Wiederholung
K*(10;k) k-Kombinationen mit Wiederholung
K(10;k) k-Kombinationen ohne Wiederholung
D(10;10-k) partielle Derangements
(bei denen nur k der 10 Elemente die Plätze wechseln)

In der modernen Kombinatorik werden diese Auswahlen oder Anordnungen auch als Abbildungen betrachtet, so dass sich die Aufgabe der Kombinatorik in diesem Zusammenhang im Wesentlichen darauf beschränken kann, diese Abbildungen zu zählen.

Anwendungen Bearbeiten

Für das Rechnen mit Wahrscheinlichkeiten auf der Basis des Wahrscheinlichkeitsbegriffs von Laplace bildet die Kombinatorik eine wichtige Grundlage.

Ein verblüffendes Phänomen der Kombinatorik ist, dass sich oftmals wenige Objekte auf vielfältige Weise kombinieren lassen. Beim Zauberwürfel können beispielsweise die 26 Elemente auf rund 43 Trillionen Arten kombiniert werden. Dieses Phänomen wird oft als kombinatorische Explosion bezeichnet und ist auch die Ursache für das Geburtstagsparadoxon.

Permutationen, Variationen und Kombinationen Bearbeiten

Begriffsabgrenzungen Bearbeiten

Aufgrund der Vielfalt der Herangehensweisen sind die Schreibweisen und Begrifflichkeiten im Bereich der Kombinatorik leider oft recht uneinheitlich. Zwar bezeichnen übereinstimmend alle Autoren die Vertauschung der Reihenfolge einer Menge von unterscheidbaren Elementen als Permutation. Wählt man dagegen von diesen Elementen nur Elemente aus, deren Reihenfolge man anschließend vertauscht, bezeichnen viele Autoren das nun als Variation, geordnete Stichprobe bzw. Kombination mit Berücksichtigung der Reihenfolge, andere dagegen (namentlich im englischsprachigen Raum) weiter als Permutation. Lässt man schließlich in einer solchen Auswahl von Elementen deren Reihenfolge außer Acht, wird solch eine Auswahl nun für gewöhnlich ungeordnete Stichprobe, Kombination ohne Berücksichtigung der Reihenfolge oder einfach nur Kombination genannt. Kombinationen sind also, sofern nichts weiter zu ihnen gesagt wird, in der Regel ungeordnet, Permutationen und/oder Variationen dagegen geordnet, wobei die Frage, ob man Permutationen als Sonderfälle von Variationen (oder umgekehrt) betrachtet, gegebenenfalls von Autor zu Autor unterschiedlich beantwortet wird.

Alles in allem gibt es also zunächst einmal drei (oder auch nur zwei) verschiedene Fragestellungen, die ihrerseits noch einmal danach unterteilt werden, ob es unter den ausgewählten Elementen auch Wiederholungen gleicher Elemente geben darf oder nicht. Ist ersteres der Fall, spricht man von Kombinationen, Variationen oder Permutationen mit Wiederholung, andernfalls solchen ohne Wiederholung. Stellt man sich schließlich vor, dass die ausgewählten Elemente dabei einer Urne oder Ähnlichem entnommen werden, wird dementsprechend auch von Stichproben mit oder ohne Zurücklegen gesprochen.

Übersicht der Terminologie
Elemente paarweise verschieden Elemente können mehrfach vorkommen
ohne Zurücklegen,
ohne Wiederholung		 mit Zurücklegen,
mit Wiederholung
geordnete Stichprobe,
mit Berücksichtigung der Reihenfolge,
d. h. Reihenfolge relevant 		Permutation Permutation ohne Wiederholung
(engl. n-permutation) 		Permutation mit Wiederholung
(engl. n-tuple)
Variation Variation ohne Wiederholung
(engl. k-permutation) 		Variation mit Wiederholung
(engl. k-tuple)
ungeordnete Stichprobe,
ohne Berücksichtigung der Reihenfolge,
d. h. Reihenfolge irrelevant 		Kombination Kombination ohne Wiederholung
(engl. k-combination) 		Kombination mit Wiederholung
(engl. k-multiset)

Anzahlen Bearbeiten

Im Folgenden bezeichnet die Zahl der vorhandenen Elemente und die Zahl ausgewählten Elemente bzw. die jeweiligen Anzahlen der Elemente, die nicht unterscheidbar sind.

Anzahl möglicher Permutationen, Variationen und Kombinationen
  ohne Wiederholung
mit Wiederholung
Permutationen
→ Fakultät → Multinomial
Variationen
→ Fallende Fakultät → k-Tupel
Kombinationen
→ Mengen (k-Teilmengen) → Multimengen

Bälle und Fächer Bearbeiten

Eine Verallgemeinerung des Urnenmodells ist ein von Gian-Carlo Rota popularisiertes Modell mit Bällen und Fächern, im Englischen nach einem Vorschlag von Joel Spencer auch Twelvefold Way („Zwölffacher Weg“) genannt. Gesucht ist dabei die Anzahl der Möglichkeiten, Bälle auf Fächer zu verteilen, wobei die Bälle und Fächer jeweils entweder unterscheidbar oder nicht unterscheidbar sind und entweder keine weitere Bedingung gilt oder in jedes Fach höchstens ein Ball kommen darf oder mindestens ein Ball kommen muss. Man erhält folgende Übersicht:

Bälle Fächer Beschränkung auf Anzahl der Bälle pro Fach
unterscheidbar? — max. 1 mind. 1

Dabei ist die Anzahl der Möglichkeiten, eine -elementige Menge in nichtleere disjunkte Teilmengen aufzuteilen (Stirling-Zahl zweiter Art), und die Anzahl der Möglichkeiten, die Zahl als Summe von positiven ganzen Zahlen ohne Beachtung der Reihenfolge darzustellen (siehe Partitionsfunktion).

Äquivalente Darstellungen Bearbeiten

Wird in einem diskreten Wahrscheinlichkeitsraum die Anzahl der möglichen Ereignisse durch eine der obigen kombinatorischen Formeln gegeben, dann können über die vollständige Zerlegung des Ereignisraums äquivalente Darstellungen für sie abgeleitet werden. Die folgenden beiden Modelle verdeutlichen dies. Es werden Bälle zufällig auf Fächer verteilt. Man betrachte die Ereignisse , dass Fächer, , mindestens einen Ball enthalten unter der Prämisse:

  1. Kein Ball wird von vornherein einem Fach zugeordnet.
  2. Jeder Ball wird von vornherein einem Fach zugeordnet, kann aber in einem anderen Fach landen.

Der erste Fall entspricht der Variante „nicht unterscheidbare Bälle, unterscheidbare Fächer“. Die vollständige Zerlegung des Ereignisraums in die disjunkten Ereignisse ergibt dann

Der zweite Fall entspricht der Variante „unterscheidbare Bälle, unterscheidbare Fächer“. Die vollständige Zerlegung des Ereignisraums analog zum ersten Fall ergibt die äquivalente Darstellung

wobei sich die zweite Summe durch Umkehrung der Summierungsreihenfolge (bzw. ) aus der ersten ergibt.

Für ist das Ereignis, dass alle Fächer mindestens einen Ball besitzen, gleich dem Ereignis, dass alle Fächer genau einen Ball besitzen, und enthält Elemente. Daraus folgt

Literatur Bearbeiten

  • Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1.
  • Karl Bosch: Elementare Einführung in die Wahrscheinlichkeitsrechnung. Vieweg, 2003, ISBN 3-528-77225-5.
  • Norbert Henze: Stochastik für Einsteiger. Springer Spektrum, 2013, ISBN 978-3-658-03076-6, doi:10.1007/978-3-658-03077-3.
  • Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1.
  • Joachim Hartung, Bärbel Elpelt, Karl-Heinz Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. Oldenbourg, 2005, ISBN 3-486-57890-1.

Weblinks Bearbeiten

Wiktionary: Kombinatorik – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
Wikibooks: Algorithmensammlung: Kombinatorik: Binomialkoeffizient – Lern- und Lehrmaterialien

Einzelnachweise Bearbeiten

  1. Richard P. Stanley: Enumerative combinatorics (Band 1), Cambridge University Press, 2. Auflage 2012, ISBN 978-1-107-01542-5, S. 79 ff. und 107 f. (englisch; Stanleys Webseite zum Buch mit der letzten Vorabversion und Errata als PDF: Enumerative Combinatorics, volume 1, second edition)
  2. Aigner: Diskrete Mathematik, 2006, S. 10
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die abzahlende Kombinatorik ist ein Teilbereich der Kombinatorik Sie beschaftigt sich mit der Bestimmung der Anzahl moglicher Anordnungen oder Auswahlenunterscheidbarer oder nicht unterscheidbarer Objekte d h ohne bzw mit Wiederholung derselben Objekte sowie mit oder ohne Beachtung ihrer Reihenfolge d h geordnet bzw ungeordnet Zahl der Variationen und Kombinationen von 10 Elementen zur k ten Klasse und der partiellen Derangements fixpunktfreie Permutationen von 10 Elementen P 10 k k Permutationen oder Variationen mit WiederholungP 10 k k Permutationen oder Variationen ohne WiederholungK 10 k k Kombinationen mit WiederholungK 10 k k Kombinationen ohne WiederholungD 10 10 k partielle Derangements bei denen nur k der 10 Elemente die Platze wechseln In der modernen Kombinatorik werden diese Auswahlen oder Anordnungen auch als Abbildungen betrachtet so dass sich die Aufgabe der Kombinatorik in diesem Zusammenhang im Wesentlichen darauf beschranken kann diese Abbildungen zu zahlen Inhaltsverzeichnis 1 Anwendungen 2 Permutationen Variationen und Kombinationen 2 1 Begriffsabgrenzungen 2 2 Anzahlen 3 Balle und Facher 4 Aquivalente Darstellungen 5 Literatur 6 Weblinks 7 EinzelnachweiseAnwendungen BearbeitenFur das Rechnen mit Wahrscheinlichkeiten auf der Basis des Wahrscheinlichkeitsbegriffs von Laplace bildet die Kombinatorik eine wichtige Grundlage Ein verbluffendes Phanomen der Kombinatorik ist dass sich oftmals wenige Objekte auf vielfaltige Weise kombinieren lassen Beim Zauberwurfel konnen beispielsweise die 26 Elemente auf rund 43 Trillionen Arten kombiniert werden Dieses Phanomen wird oft als kombinatorische Explosion bezeichnet und ist auch die Ursache fur das Geburtstagsparadoxon Permutationen Variationen und Kombinationen Bearbeiten Hauptartikel Permutation Variation Kombinatorik und Kombination Kombinatorik Begriffsabgrenzungen Bearbeiten Aufgrund der Vielfalt der Herangehensweisen sind die Schreibweisen und Begrifflichkeiten im Bereich der Kombinatorik leider oft recht uneinheitlich Zwar bezeichnen ubereinstimmend alle Autoren die Vertauschung der Reihenfolge einer Menge von n displaystyle n nbsp unterscheidbaren Elementen als Permutation Wahlt man dagegen von diesen n displaystyle n nbsp Elementen nur k lt n displaystyle k lt n nbsp Elemente aus deren Reihenfolge man anschliessend vertauscht bezeichnen viele Autoren das nun als Variation geordnete Stichprobe bzw Kombination mit Berucksichtigung der Reihenfolge andere dagegen namentlich im englischsprachigen Raum weiter als Permutation Lasst man schliesslich in einer solchen Auswahl von Elementen deren Reihenfolge ausser Acht wird solch eine Auswahl nun fur gewohnlich ungeordnete Stichprobe Kombination ohne Berucksichtigung der Reihenfolge oder einfach nur Kombination genannt Kombinationen sind also sofern nichts weiter zu ihnen gesagt wird in der Regel ungeordnet Permutationen und oder Variationen dagegen geordnet wobei die Frage ob man Permutationen als Sonderfalle von Variationen oder umgekehrt betrachtet gegebenenfalls von Autor zu Autor unterschiedlich beantwortet wird Alles in allem gibt es also zunachst einmal drei oder auch nur zwei verschiedene Fragestellungen die ihrerseits noch einmal danach unterteilt werden ob es unter den ausgewahlten Elementen auch Wiederholungen gleicher Elemente geben darf oder nicht Ist ersteres der Fall spricht man von Kombinationen Variationen oder Permutationen mit Wiederholung andernfalls solchen ohne Wiederholung Stellt man sich schliesslich vor dass die ausgewahlten Elemente dabei einer Urne oder Ahnlichem entnommen werden wird dementsprechend auch von Stichproben mit oder ohne Zurucklegen gesprochen Ubersicht der Terminologie Elemente paarweise verschieden Elemente konnen mehrfach vorkommenohne Zurucklegen ohne Wiederholung mit Zurucklegen mit Wiederholunggeordnete Stichprobe mit Berucksichtigung der Reihenfolge d h Reihenfolge relevant k n displaystyle k n nbsp Permutation Permutation ohne Wiederholung engl n permutation Permutation mit Wiederholung engl n tuple k lt n displaystyle k lt n nbsp Variation Variation ohne Wiederholung engl k permutation Variation mit Wiederholung engl k tuple ungeordnete Stichprobe ohne Berucksichtigung der Reihenfolge d h Reihenfolge irrelevant Kombination Kombination ohne Wiederholung engl k combination Kombination mit Wiederholung engl k multiset Anzahlen Bearbeiten Im Folgenden bezeichnet n displaystyle n nbsp die Zahl der vorhandenen Elemente und k displaystyle k nbsp die Zahl ausgewahlten Elemente bzw k 1 k s displaystyle k 1 ldots k s nbsp die jeweiligen Anzahlen der Elemente die nicht unterscheidbar sind Anzahl moglicher Permutationen Variationen und Kombinationen ohne Wiederholung a b c a b c displaystyle a b c a b c nbsp mit Wiederholung a a b a a b displaystyle a a b a a b nbsp Permutationen a b b a displaystyle a b neq b a nbsp n displaystyle n nbsp k 1 k s k 1 k s n k 1 k s n k 1 k s displaystyle frac k 1 ldots k s k 1 cdot ldots cdot k s frac n k 1 cdot ldots cdot k s binom n k 1 ldots k s nbsp Fakultat MultinomialVariationen a b b a displaystyle a b neq b a nbsp n k n k k n n k displaystyle n underline k n choose k cdot k frac n left n k right nbsp n k displaystyle n k nbsp Fallende Fakultat k TupelKombinationen a b b a displaystyle a b b a nbsp n k n n k k displaystyle n choose k frac n left n k right cdot k nbsp n k n k 1 k n k 1 n 1 k displaystyle left n choose k right n k 1 choose k frac left n k 1 right left n 1 right cdot k nbsp Mengen k Teilmengen MultimengenBalle und Facher BearbeitenEine Verallgemeinerung des Urnenmodells ist ein von Gian Carlo Rota popularisiertes Modell mit Ballen und Fachern im Englischen nach einem Vorschlag von Joel Spencer auch Twelvefold Way Zwolffacher Weg genannt 1 2 Gesucht ist dabei die Anzahl der Moglichkeiten k displaystyle k nbsp Balle auf n displaystyle n nbsp Facher zu verteilen wobei die Balle und Facher jeweils entweder unterscheidbar oder nicht unterscheidbar sind und entweder keine weitere Bedingung gilt oder in jedes Fach hochstens ein Ball kommen darf oder mindestens ein Ball kommen muss Man erhalt folgende Ubersicht k displaystyle k nbsp Balle n displaystyle n nbsp Facher Beschrankung auf Anzahl der Balle pro Fachunterscheidbar max 1 mind 1 displaystyle checkmark nbsp displaystyle checkmark nbsp n k displaystyle n k nbsp n k n n k k n k displaystyle n underline k tfrac n n k k tbinom n k nbsp n S k n displaystyle n S k n nbsp displaystyle times nbsp displaystyle checkmark nbsp n k k n 1 n 1 displaystyle left tbinom n k right tbinom k n 1 n 1 nbsp n k displaystyle tbinom n k nbsp n k n k 1 n 1 displaystyle left tbinom n k n right tbinom k 1 n 1 nbsp displaystyle checkmark nbsp displaystyle times nbsp r 0 n S k r displaystyle sum r 0 n S k r nbsp 1 k n 0 k gt n displaystyle begin array lll 1 amp amp k leq n 0 amp amp k gt n end array nbsp S k n displaystyle S k n nbsp displaystyle times nbsp displaystyle times nbsp r 0 n P k r P k n n displaystyle sum r 0 n P k r P k n n nbsp 1 k n 0 k gt n displaystyle begin array lll 1 amp amp k leq n 0 amp amp k gt n end array nbsp P k n displaystyle P k n nbsp Dabei ist S k n displaystyle S k n nbsp die Anzahl der Moglichkeiten eine k displaystyle k nbsp elementige Menge in n displaystyle n nbsp nichtleere disjunkte Teilmengen aufzuteilen Stirling Zahl zweiter Art und P k n displaystyle P k n nbsp die Anzahl der Moglichkeiten die Zahl k displaystyle k nbsp als Summe von n displaystyle n nbsp positiven ganzen Zahlen ohne Beachtung der Reihenfolge darzustellen siehe Partitionsfunktion Aquivalente Darstellungen BearbeitenWird in einem diskreten Wahrscheinlichkeitsraum W P displaystyle Omega P nbsp die Anzahl der moglichen Ereignisse durch eine der obigen kombinatorischen Formeln gegeben dann konnen uber die vollstandige Zerlegung des Ereignisraums aquivalente Darstellungen fur sie abgeleitet werden Die folgenden beiden Modelle verdeutlichen dies Es werden k displaystyle k nbsp Balle zufallig auf n k displaystyle n leq k nbsp Facher verteilt Man betrachte die Ereignisse E j displaystyle E j nbsp dass j displaystyle j nbsp Facher j 1 n displaystyle j 1 ldots n nbsp mindestens einen Ball enthalten unter der Pramisse Kein Ball wird von vornherein einem Fach zugeordnet Jeder Ball wird von vornherein einem Fach zugeordnet kann aber in einem anderen Fach landen Der erste Fall entspricht der Variante nicht unterscheidbare Balle unterscheidbare Facher Die vollstandige Zerlegung des Ereignisraums in die disjunkten Ereignisse E j displaystyle E j nbsp ergibt dann W n k 1 k j 1 n n j k 1 k j displaystyle Omega binom n k 1 k sum j 1 n binom n j binom k 1 k j nbsp Der zweite Fall entspricht der Variante unterscheidbare Balle unterscheidbare Facher Die vollstandige Zerlegung des Ereignisraums analog zum ersten Fall ergibt die aquivalente Darstellung W n k j 1 n n j i 0 j 1 1 i j j i j i k j 1 n n j 1 j i 1 j 1 i j i i k displaystyle Omega n k sum j 1 n binom n j sum i 0 j 1 1 i binom j j i j i k sum j 1 n binom n j 1 j sum i 1 j 1 i binom j i i k nbsp wobei sich die zweite Summe durch Umkehrung der Summierungsreihenfolge bzw i j i displaystyle i to j i nbsp aus der ersten ergibt Fur n k displaystyle n k nbsp ist das Ereignis dass alle Facher mindestens einen Ball besitzen gleich dem Ereignis dass alle Facher genau einen Ball besitzen und enthalt n displaystyle n nbsp Elemente Daraus folgt n i 0 n 1 1 i n n i n i n 1 n i 1 n 1 i n i i n displaystyle n sum i 0 n 1 1 i binom n n i n i n 1 n sum i 1 n 1 i binom n i i n nbsp Literatur BearbeitenMartin Aigner Diskrete Mathematik Vieweg 2006 ISBN 3 8348 9039 1 Karl Bosch Elementare Einfuhrung in die Wahrscheinlichkeitsrechnung Vieweg 2003 ISBN 3 528 77225 5 Norbert Henze Stochastik fur Einsteiger Springer Spektrum 2013 ISBN 978 3 658 03076 6 doi 10 1007 978 3 658 03077 3 Konrad Jacobs Dieter Jungnickel Einfuhrung in die Kombinatorik de Gruyter 2003 ISBN 3 11 016727 1 Joachim Hartung Barbel Elpelt Karl Heinz Klosener Statistik Lehr und Handbuch der angewandten Statistik Oldenbourg 2005 ISBN 3 486 57890 1 Weblinks Bearbeiten nbsp Wiktionary Kombinatorik Bedeutungserklarungen Wortherkunft Synonyme Ubersetzungen nbsp Wikibooks Algorithmensammlung Kombinatorik Binomialkoeffizient Lern und Lehrmaterialien V N Sachkov Combinatorial analysis In Michiel Hazewinkel Hrsg Encyclopedia of Mathematics Springer Verlag und EMS Press Berlin 2002 ISBN 1 55608 010 7 englisch encyclopediaofmath org Modul Kombinatorik beim MathePrisma Michael Stoll Abzahlende Kombinatorik PDF 554 kB Vorlesungsskript Empfehlungen zur Kombinatorik in der Schule PDF 612 kB aus Stochastik in der Schule 33 2013 1 S 21 25Einzelnachweise Bearbeiten Richard P Stanley Enumerative combinatorics Band 1 Cambridge University Press 2 Auflage 2012 ISBN 978 1 107 01542 5 S 79 ff und 107 f englisch Stanleys Webseite zum Buch mit der letzten Vorabversion und Errata als PDF Enumerative Combinatorics volume 1 second edition Aigner Diskrete Mathematik 2006 S 10 Abgerufen von https de wikipedia org w index php title Abzahlende Kombinatorik amp oldid 237006160