Kombinatorik

Kombinatorik ist ein Teilgebiet der Mathematik, das sich mit der Bestimmung der

Zahl möglicher Anordnungen oder Auswahlen von
unterscheidbaren oder nicht unterscheidbaren Objekten
mit oder ohne Beachtung der Reihenfolge

beschäftigt.

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

Inhaltsverzeichnis

1 Permutationen (Anordnungen)

1.1 Unterscheidbare Objekte mit Beachtung der Reihenfolge
1.2 Objekte mehrerer Klassen mit Beachtung der Reihenfolge

2 Auswahlen mit Beachtung der Reihenfolge (Variationen)

2.1 Variation ohne Zurücklegen
2.2 Variation mit Zurücklegen

3 Auswahlen ohne Beachtung der Reihenfolge (Kombinationen)

3.1 Kombination ohne Zurücklegen
3.2 Kombination mit Zurücklegen (Repetition)

4 Weitere Informationen

4.1 Große Zahlen
4.2 Siehe auch
4.3 Weblinks

Permutationen (Anordnungen)

Unterscheidbare Objekte mit Beachtung der Reihenfolge

Als einführendes Beispiel mag die Zahl der Anordnungen von sechs unterscheidbaren Objekten mit Beachtung der Reihenfolge dienen. Offensichtlich kann jedes der Objekte "auf den ersten Platz gelangen", es gibt also sechs Möglichkeiten, den ersten Platz zu besetzen. Wenn der erste Platz besetzt ist, bleiben noch fünf Kandidaten für den zweiten Platz, ist auch dieser besetzt, nur noch vier Kandidaten für den dritten Platz, und so fort. Für den vorletzten Platz bleiben schließlich nur noch zwei Objekte übrig, und der letzte Platz muss mit dem "übrig gebliebenen" Objekt besetzt werden.

Es gibt also 6 * 5 * 4 * 3 * 2 * 1 oder 6 ! = 720 Möglichkeiten, sechs unterscheidbare Objekte anzuordnen. Das Ausrufezeichen steht für "Fakultät" und wird auch so gelesen, also "Sechs Fakultät". Allgemein:

Anzahl der Permutationen von

n

verschiedenen Elementen:

n!

Wenn den Kandidaten feste Plätze zugeordnet werden, und man wissen möchte, wieviele Möglichkeiten existieren, so daß sich kein einziger Kandidat auf seinen vorgesehenen Platz setzt, berechnet man das über die Subfakultät !n. Bei den sechs Kandidaten sind das !6 = 265 Möglichkeiten.

Objekte mehrerer Klassen mit Beachtung der Reihenfolge

Für die Zahl der möglichen Anordnungen von Objekten aus mehreren Klassen, die untereinander jeweils innerhalb einer Klasse nicht unterscheidbar sind, ist es hilfreich, zunächst die mögliche Zahl der Anordnungen der Objekte zu betrachten und dann zu überlegen, wieviele dieser Anordnungen nicht unterscheidbar sind. Die Zahl der möglichen Anordnungen bei unterscheidbaren Objekten wird durch die Zahl der nicht unterscheidbaren Anordnungen geteilt.

Wenn die mögliche Zahl von Anordnungen von zwei Objekten einer ersten Klasse, drei Objekten einer zweiten Klasse und fünf Objekten einer dritten Klasse ermittelt werden soll, dann gibt es zunächst (2 + 3 + 5)! oder 3.628.800 mögliche Anordnungen. Weil aber Anordnungen nicht unterscheidbar sind, bei denen nur Objekte einer Klasse untereinander den Platz getauscht haben, weil also jeweils 2! * 3! * 5! oder 1.440 der möglichen Anordnungen gleich erscheinen, gibt es nur 3.628.800/1.440 oder 2.520 unterscheidbare Anordnungen dieser Elemente. Allgemein:

Anzahl der Permutationen von

n

Elementen, die in

k

Gruppen von je

l 1, l 2,..., l k

gleichen Elementen $(\sum^k_{i=1} l_i = n)$ fallen: $\frac{n!}{l_1! l_2!...l_k!}$

Auswahlen mit Beachtung der Reihenfolge (Variationen)

Variation ohne Zurücklegen

k Plätze sollen mit jeweils einem aus n Objekten besetzt werden, wobei jedes Objekt maximal einen Platz besetzen darf (also muss k<=n sein). Hier gibt es

$\frac{n!}{(n-k)!}$

Möglichkeiten.

Anmerkung: Ein wissenschaftlicher Taschenrechner erspart hierbei durch die Funktion(staste) "nPr" viel Tipparbeit: i.d.R. Eingabe n-Wert, Taste "nPr", Eingabe k-Wert, Taste "=". Außerdem führen Fakultäten von großen Zahlen zum Überlauf, zum Beispiel 300P3=26730600 lässt sich kaum mit der Fakultät berechnen.

Variation mit Zurücklegen

Wenn aus n Objekten k Objekte mit Zurücklegen und mit Beachtung der Reihenfolge ausgewählt werden sollen, dann kann jedes der n Objekte auf jedem der k Plätze der Auswahl erscheinen, es gibt demzufolge

n k

mögliche Auswahlen.

Wenn also aus 3 Objekten 11 mal mit Zurücklegen gezogen wird, dann sind 3¹¹ = 177.147 verschiedene Auswahlen möglich. Als Beispiel aus der Genetik mag die Anzahl möglicher 3er Tupel (Codons) bei 4 verschiedenen Nukleotidbasen dienen: 4³ = 64; die tatsächliche Anzahl kodierter Aminosäuren ist geringer (22 (plus Start- und Stopcodons)), da der genetische Code degeneriert ist.

Auswahlen ohne Beachtung der Reihenfolge (Kombinationen)

Im Gegensatz zu den Variationen werden bei den Kombinationen die Anordnungen außer acht gelassen, d.h. "abc" ist gleichwertig mit "bca". Es muss also weniger Kombinationen als Variationen geben.

Kombination ohne Zurücklegen

Auswahlprobleme ohne Zurücklegen können als Anordnungsprobleme aufgefasst werden. Die Zahl der möglichen Auswahlen kann ermittelt werden, indem die Zahl der Anordnungen ermittelt wird, bei denen die ausgewählten Objekte auf ausgezeichneten Plätzen angeordnet sind.

Dieses Auswahlproblem kann auf die Ermittlung aller Anordnungen zurückgeführt werden, bei denen die ausgewählten Objekte auf den ersten Plätzen landen, wobei es weder bei den ausgewählten noch bei den nicht ausgewählten Objekten auf die Reihenfolge ankommt.

Wenn aus n Objekten k ohne Zurücklegen und ohne Beachtung der Reihenfolge ausgewählt werden sollen, so gibt es jeweils die Klasse der k ausgewählten Objekte und die Klasse der (n-k) nicht ausgewählten Objekte, in der es auf die Reihenfolge nicht ankommt. Dabei sind k und n-k in der Formel austauschbar, da man die n Objekte in zwei Teilmengen teilt, welche davon die interessierende ist, ist für die Anzahl der möglichen Aufteilungen nicht entscheidend.

Demzufolge gibt es ${n \choose k} = {n \choose n-k} = \frac{n!}{k! (n-k)!}$ mögliche derartige Auswahlen.

Dieser häufig benötigte Ausdruck wird als Binomialkoeffizient bezeichnet.

Wenn aus 49 Objekten nun 6 ohne Zurücklegen und ohne Beachtung der Reihenfolge ausgewählt werden sollen, wie dies zum Beispiel bei der Ziehung der Lottozahlen der Fall ist, so gibt es 13.983.816 mögliche Auswahlen.

Ein wissenschaftlicher Taschenrechner erspart hierbei durch die Funktion(staste) "nCr" viel Tipparbeit: i.d.R. Eingabe n-Wert, Taste "nCr", Eingabe k-Wert, Taste "=".

Kombination mit Zurücklegen (Repetition)

${n+k-1 \choose k} = \frac{(n+k-1)!}{k! (n-1)!}$

Eine Anwendung davon ist das Gummibärchen-Orakel. Dort wählt man k=5 Bärchen von n=5 Elementen aus (5 Farben). Demnach gibt es (5+5-1)! / (5!*(5-1)!) = 9! / (5!*4!) = 126 verschiedene Kombinationen.

Weitere Informationen

Große Zahlen

Mit eines der verblüffendsten Phänomene der Kombinatorik ist die oftmals geringe Anzahl von Objekten, deren Kombination sehr schnell zu sehr großen Zahlen führt. Berüchtigt ist etwa Rubiks Würfel mit seinen rund 43 Trillionen Kombinationen. Dieses Phänomen wird oft als Kombinatorische Explosion bezeichnet und ist auch die Ursache für das so genannte Geburtstagsparadoxon.

Aber auch bei der Simulation des menschlichen Gehirns als Netzwerk einzelner Neuronen explodiert die Anzahl der möglichen Verschaltungsmuster schon bei wenigen Punkten:

Neuronen	Anzahl der Verschaltungsmuster
2	$21 = 2$
3	$23 = 8$
4	$26 = 64$
5	$210 = 1024$
6	$215 = 32768$

Auch hier steigt die Anzahl der möglichen Kombinationen rapide an. In welchem Maße alle vorstellbaren Grenzen schon nach kurzer Zeit gesprengt werden, zeigt folgende Überlegung:

Dividiert man die Masse der Sonne durch die Masse eines Protons, so erhält man eine grobe Abschätzung dafür, aus wievielen Nukleonen die Sonne besteht. Es ergibt sich ein Wert in der Größenordnung $1057$ . Bedenkt man nun, daß unsere Milchstraße aus rund 100 Milliarden Sternen besteht und der beobachtbare Teil des Universums seinerseits 100 Milliarden Galaxien enthält, so kommt man auf eine grobe Schätzung der Anzahl von Nukleonen, aus denen das Universum besteht: $10^{57}\cdot 100\cdot 10^9\cdot 100\cdot 10^9=10^{79}$

Nun kann man sich die Frage stellen, wieviele Neuronen man benötigt, um eine Anzahl von möglichen Verschaltungsmustern zu erreichen, die größer ist als $1079$ . Auch hier ist die Antwort verblüffend: Bei nur 24 Neuronen ergeben sich bereits $2^{276}\approx 10^{83}$ Möglichkeiten - mehr als es Protonen und Neutronen im beobachtbaren Universum gibt. Unser Gehirn besteht jedoch aus rund 15 Milliarden Nervenzellen ...

Siehe auch

Lateinisches Quadrat