Abzählende Kombinatorik - LinkFang.de





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“).

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

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

Begriffsabgrenzungen

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 [math]n[/math] unterscheidbaren Elementen als Permutation. Wählt man dagegen von diesen [math]n[/math] Elementen nur [math]k \lt n[/math] 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:

Ohne Wiederholung bzw. Zurücklegen Mit Wiederholung bzw. Zurücklegen
Mit Berücksichtigung der Reihenfolge
und k = n
Permutation ohne Wiederholung
(engl. n-permutation)
Permutation mit Wiederholung
Mit Berücksichtigung der Reihenfolge
und k < n
Variation ohne Wiederholung
(engl. k-permutation)
Variation mit Wiederholung
Ohne Berücksichtigung der Reihenfolge
und k < n
Kombination ohne Wiederholung
(engl. k-combination)
Kombination mit Wiederholung

Anzahlen

Bezeichnet [math]n[/math] die Zahl der vorhandenen Elemente und [math]r, s, \ldots , t[/math] die Zahl der Elemente, die nicht unterscheidbar sind, dann gilt für die Anzahl möglicher Permutationen:

  ohne Wiederholung/Zurücklegen
[math](a,b,c)[/math]
mit Wiederholung/Zurücklegen
[math](a,a,b)[/math]
Permutation
[math](a,b) \ne (b,a)[/math]
[math]~n!~[/math] [math]\frac{(r + s + \ldots + t)!}{r! \cdot s! \cdot \ldots \cdot t!} = \frac{n!}{r! \cdot s! \cdot \ldots \cdot t!}[/math]

Bezeichnet [math]n[/math] die Zahl der vorhandenen Elemente und [math]k[/math] die Zahl der Elemente, die ausgewählt werden, dann gilt für die Anzahl möglicher Variationen und Kombinationen:

  ohne Wiederholung/Zurücklegen
[math](a,b,c), \{a,b,c\}[/math]
mit Wiederholung/Zurücklegen
[math](a,a,b), \{a,a,b\}[/math]
Variation
[math](a,b) \ne (b,a)[/math]
[math]{n \choose k}\cdot {k!} = \frac{n!}{ \left( n-k \right) !}[/math] [math]~n^k~[/math]
Kombination
[math]\{a,b\} = \{b,a\}[/math]
[math]{n \choose k} = \frac{n!}{{\left( n-k \right) !} \cdot k!}[/math] [math]\left(\!\!{n \choose k}\!\!\right) = {n + k -1 \choose k} = \frac{ \left( n + k -1 \right)! }{{\left( n-1 \right)! \cdot k!} }[/math]

Bälle und Fächer

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.[1][2] Gesucht ist dabei die Anzahl der Möglichkeiten, [math]k[/math] Bälle auf [math]n[/math] 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:

beliebig viele Bälle pro Fach höchstens ein Ball pro Fach mindestens ein Ball pro Fach
[math]k[/math] unterscheidbare Bälle
[math]n[/math] unterscheidbare Fächer
[math]n^k[/math] [math]\frac{n!}{(n-k)!} = k!\,\binom{n}{k}[/math] [math]n!\,S_{k,n}[/math]
[math]k[/math] nicht unterscheidbare Bälle
[math]n[/math] unterscheidbare Fächer
[math]\binom{k+n-1}{k} = \left(\!\!\binom{n}{k}\!\!\right)[/math] [math]\binom{n}{k}[/math] [math]\binom{k-1}{n-1} = \left(\!\!\binom{n}{k-n}\!\!\right)[/math]
[math]k[/math] unterscheidbare Bälle
[math]n[/math] nicht unterscheidbare Fächer
[math]S_{k,0} + S_{k,1} + \cdots + S_{k,n}[/math] [math]\begin{array}{lll} 1 & \text{für} & k \leq n \\ 0 & \text{für} & k \gt n \end{array}[/math] [math]S_{k,n}[/math]
[math]k[/math] nicht unterscheidbare Bälle
[math]n[/math] nicht unterscheidbare Fächer
[math]P_{k,0} + P_{k,1} + \cdots + P_{k,n} = P_{k+n,n}[/math] [math]\begin{array}{lll} 1 & \text{für} & k \leq n\\ 0 & \text{für} & k \gt n \end{array}[/math] [math]P_{k,n}[/math]

Dabei ist [math]S_{k,n}[/math] die Anzahl der Möglichkeiten, eine [math]k[/math]-elementige Menge in [math]n[/math] nichtleere disjunkte Teilmengen aufzuteilen (Stirling-Zahl zweiter Art), und [math]P_{k,n}[/math] die Anzahl der Möglichkeiten, die Zahl [math]k[/math] als Summe von [math]n[/math] positiven ganzen Zahlen ohne Beachtung der Reihenfolge darzustellen (siehe Partitionsfunktion).

Äquivalente Darstellungen

Wird in einem diskreten Wahrscheinlichkeitsraum [math](\Omega,P)[/math] 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 [math]k[/math] Bälle zufällig auf [math]n \le k[/math] Fächer verteilt. Man betrachte die Ereignisse [math]E_{j}[/math], dass [math]j[/math] Fächer, [math]j=1, \ldots ,n[/math], 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 [math]E_{j}[/math] ergibt dann

[math]|\Omega| = \binom {n+k-1} {k} = \sum_{j=1}^ {n} \binom {n} {j} \binom {k-1} {k-j}[/math].

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

[math]|\Omega| = n^k = \sum_{j=1}^ {n}\binom{n}{j}\sum_{i=0}^{j-1}(-1)^{i}\binom{j}{j-i}(j-i)^{k}[/math].

Für [math]n=k[/math] 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 [math]n![/math] Elemente. Daraus folgt

[math]n! = \sum_{i=0}^{n-1}(-1)^{i}\binom{n}{n-i}(n-i)^{n}[/math].

Literatur

Einzelnachweise

  1. Richard P. Stanley: Enumerative combinatorics (Band 1), Cambridge University Press, 2. Auflage 2012, ISBN 978-1-10-701542-5, S. 79 ff. und 107 f. (englisch; Stanleys Webseite zum Buch mit der letzten Vorabversion und Errata als PDF-Dateien: Enumerative Combinatorics, volume 1, second edition )
  2. Aigner: Diskrete Mathematik, 2006, S. 10

Weblinks

 Wiktionary: Kombinatorik – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Abzählende Kombinatorik (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.