Kombinatorik

Die Kombinatorik beschäftigt sich mit der Bestimmung der
  • Zahl möglicher Anordnungen oder Auswahlen von
  • unterscheidbaren oder nicht unterscheidbaren Objekten
  • mit oder ohne Beachtung der Reihenfolge.
Für das Rechnen mit Wahrscheinlichkeiten bildet die Kombinatorik eine wichtige Grundlage.

Anordnungen (Permutationen)

Permutation (= Zahl der Reihenfolgen): "Jede mögliche Anordnung von nn Elementen, in der alle Elemente verwendet werden, heißt Permutation dieser Elemente."

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.
Permutation.png
Anordnungen für drei Kugeln
Es gibt also 6⋅5⋅4⋅3⋅2⋅1 6·5·4·3·2·1 oder 6!=7206! = 720 Möglichkeiten, sechs unterscheidbare Objekte anzuordnen. Das Ausrufezeichen steht für "Fakultät" und wird auch so gelesen. Allgemein: Anzahl der Permutationen von nn verschiedenen Elementen:
n! n!
In der nebenstehenden [!Abbildung] werden die sechs Möglichkeiten drei verschieden farbige Kugeln anzuordnen gezeigt (3!=63!=6).

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)!(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!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 nn Elementen, die in kk Gruppen von je l1,l2,…,lkl_1, l_2, \dots , l_k gleichen Elementen (∑i=1kli=n)(\sum\limits^k_{i=1} l_i = n) fallen:
n!l1!l2!…lk!\dfrac{n!}{l_1! l_2!\dots l_k!}

Auswahlen mit Beachtung der Reihenfolge (Variationen)

Variation ohne Zurücklegen

kk Plätze sollen mit jeweils einem aus nn Objekten besetzt werden, wobei jedes Objekt maximal einen Platz besetzen darf (also muss k≤nk\le n sein). Hier gibt es
n!(n−k)! \dfrac{n!}{(n-k)!}
Möglichkeiten.

Variation mit Zurücklegen

Wenn aus nn Objekten kk Objekte mit Zurücklegen und mit Beachtung der Reihenfolge ausgewählt werden sollen, dann kann jedes der nn Objekte auf jedem der kk Plätze der Auswahl erscheinen, es gibt demzufolge
nkn^k
mögliche Auswahlen.
Wenn also aus 33 Objekten 1111 mal mit Zurücklegen gezogen wird, dann sind 3113^{11} = 177.147 verschiedene Auswahlen möglich.

Beispiele

Bei einem Zahlenschloss mit 3 Ringen und je 10 Ziffern gibt es 103=100010^{3} = 1000 verschiedene Kombinationen.
Eine Binärzahl kennt 2 Zustände (00 und 11). Mit einer Reihenfolge von xx Zahlen können 2x2^{x} verschiedene Variationen entstehen. Bei 4 Stellen yyyyyyyy ergibt dies 24=16 2^{4} = 16 verschiedene Möglichkeiten.

Auswählen 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 nn Objekten kk ohne Zurücklegen und ohne Beachtung der Reihenfolge ausgewählt werden sollen, so gibt es jeweils die Klasse der kk ausgewählten Objekte und die Klasse der (n−kn-k) nicht ausgewählten Objekte, in der es auf die Reihenfolge nicht ankommt. Dabei sind kk und n−kn-k in der Formel austauschbar, da man die nn Objekte in zwei Teilmengen teilt, welche davon die interessierende ist, ist für die Anzahl der möglichen Aufteilungen nicht entscheidend.
Demzufolge gibt es
(nk)=(nn−k)=n!k!(n−k)!\chooseNT{n}{k} = \chooseNT{n}{n-k} = \dfrac{n!}{k! (n-k)!} =n(n−1)(n−2)…(n−k+1)k!= \dfrac{n (n-1)(n-2) \dots (n-k+1)}{k!}
mögliche derartige Auswahlen.
Dieser häufig benötigte Ausdruck wird als Binomialkoeffizient bezeichnet.

Beispiel

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.

Kombination mit Zurücklegen (Repetition)

(n+k−1k)=(n+k−1)!k!(n−1)! \chooseNT{n+k-1}{k} = \dfrac{(n+k-1)!}{k! (n-1)!}

Beispiel

Wir ziehen von k=4k=4 Kugeln, die nach jeder Ziehung zurückgelegt werden, aus einem Topf mit n=10n=10 unterschiedlichen Kugeln. Wenn man die Reihenfolge der Ziehungen nicht beachtet, so gibt es (10+4−1)!4!(10−1)!\dfrac{(10+4-1)!}{4! (10-1)!} =13!4! 9!=715=\dfrac{13!}{4!\, 9!} = 715 verschiedene Kombinationen.

Zusammenfassung

  Variation (Mit Beachtung der Reihenfolge)
{a,b}≠{b,a}\left\{ a{,}b \right\} \ne \left\{ b{,}a \right\} 		Kombination (Ohne Beachtung der Reihenfolge)
{a,b}={b,a}\left\{ a{,}b \right\} = \left\{ b{,}a \right\} 		Permutation
M={l1 a, l2 b, …, lk x}M = \left\{ l_1 \, a,\, l_2 \, b ,\, \dots ,\, l_k \, x \right\}
mit Wiederholung (Mit Zurücklegen)
{a, a, b}\left\{ a ,\, a ,\, b \right\}
Binomialverteilung 		nk n^k \, (n+k−1)!k!⋅(n−1)!\dfrac{\braceNT{ n + k - 1 }! }{k! \cdot {\braceNT{ n-1 }!} } =(n−1+kk)= \chooseNT{n - 1 + k}{k} n!∏i=1kli!\dfrac{n!}{ \prod\limits_{i=1}^k l_i! }  =\ = n!l1! l2!…lk!\dfrac{n!}{l_1! \, l_2!\dots l_k!}
ohne Wiederholung (Ohne Zurücklegen)
{a, b, c}\left\{ a ,\, b ,\, c \right\}
Hypergeometrische Verteilung 		n!(n−k)!\dfrac{n!}{ \braceNT{ n-k } !} =(nk)⋅k!=\chooseNT{n}{k}{\cdot k!} n!k!⋅(n−k)!\dfrac{n!}{k! \cdot {\braceNT{ n-k } !}} =(nk)=\chooseNT{n}{k} n! n! \,
 
 

Ein Mathematiker ist eine Maschine, die Kaffee in Theoreme verwandelt.

Paul Erdös

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung