Kombination, Variation, Permutation

Kombination, Variation, Permutation

  • 5. Februar 2018
  • Posted by: Mika
Keine Kommentare

Im Folgenden wird der Unterschied zwischen Kombination, Variation und Permutation erklärt. Bei der Bestimmung der möglichen und günstigen Fälle eines Zufallsexperimentes zerlegst Du zuerst die Dich interessierenden Ausgänge in zugrundeliegende Elementarereignisse und betrachtest deren Anordnung. Möchtest Du beispielsweise wissen, wie wahrscheinlich es ist, dass Dir beim Kartengeben drei Buben zugeteilt werden, so ist das Elementarereignis das Erhalten einer bestimmten Karte.

Es kommt dabei auf die folgenden Punkte an:

  • Stammen alle Elemente der  Stichprobe aus der Grundmenge?
  • Ist die Anordnung bzw. Reihenfolge des Auftretens bedeutsam?
  • Liegen Wiederholungen der Elementarereignisse vor?

Beim Kartenspielen macht es zum Beispiel einen Unterschied, ob Du beim Geben alle Karten sofort auf die Spieler aufteilst und das gesamte Blatt bei Spielbeginn im Umlauf ist, oder ob jeder Spieler etwa fünf Karten erhält und die restlichen Karten im Stock verbleiben. Anfangs spielt die Austeilreihenfolge der Karten keine Rolle. Wartest Du allerdings während des Spiels auf eine bestimmte Karte, so ist es wichtig, wann Du sie erhältst.

Was ist eine Permutation?

Unter einer Permutation versteht man die Anordnung von n unterscheidbaren Elementen in einer bestimmten Reihenfolge.

Im Falle, dass keine Wiederholungen auftreten, ist die Anzahl der möglichen Permutationen aus n Elementen mit n Fakultät gegeben:

    \begin{equation*} n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 1 \end{equation*}

Drei Stifte (n=3) in den Farben rot (r), schwarz (S) und blau(B) werden beispielsweise zufällig an drei Personen verteilt. Dann gibt es dafür 3!=6 verschiedene Möglichkeiten. Solange noch kein Stift verteilt ist, gibt es für die erste Person drei Stifte, die sie erhalten kann. Ist dann der erste Stift vergeben, so bleiben für die zweite Person noch zwei Möglichkeiten. Nach Austeilen des zweiten Stiftes ist für die dritte Person schließlich nur noch eine Möglichkeit übrig:

Person 1 erhält Person 2 erhält Person 3 erhält
R S B
R B S
S R B
S B R
B R S
B S R

Permutationen mit Wiederholungen

Bei Permutationen mit Wiederholungen sind im Gegensatz dazu nicht alle Elemente unterscheidbar. Hast Du n Elemente, von denen m identisch sind, so ist die Anzahl der möglichen unterschiedlichen Anordnungen nämlich geringer:

    \begin{equation*} \frac {n!} {m!} = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-m+1 )\end{equation*}

Hast Du von den drei Stiften (n=3) zwei in den Farben schwarz (S) und einen in rot (R)vorliegen und möchtest sie auf drei Personen verteilen, so gibt es somit m=2 identische Objekte und Du erhältst nur noch

    \begin{equation*} \frac {3!} {2!} = 3 \end{equation*}

mögliche unterschiedliche Anordnungen.

Person 1 erhält Person 2 erhält Person 3 erhält
R S S
S S R
S R S

Gibt es allgemein unter den n Objekten s Objekte, die jeweils in n_s Wiederholungen vorkommen, so ist die Anzahl möglicher Permutationen also durch

    \begin{equation*} \frac {n!} {n_1! \cdot n_2!\cdot ... \cdot n_s!} = \left( \begin {array} {11} n\\ {n_1!,n_2!,...n_s! }\end{array} \right) \end{equation*}

gegeben.

Was ist eine Variation?

Eine Variation aus k von n Elementen der Grundmenge ist ein Teil der Grundmenge, bei der es auch auf die Reihenfolge der Anordnung ankommt. Sind alle Elemente voneinander unterscheidbar, spricht man von einer Variation ohne Wiederholung und die Anzahl unterschiedlicher Variationen von k aus n Elementen beträgt:

    \begin{equation*} \frac {n! } { (n-k)!} \end{equation*}

Von 6 unterschiedlichen Bildern (B_1 bis B_6) werden Dir beispielsweise zufällig 2 Bilder zugeteilt. Beim ersten Bild könntest Du also jedes der sechs Bilder erhalten, beim zweiten Bild nur noch eins der fünf verbliebenen Bilder. Die Anzahl der insgesamt möglichen Variationen beträgt also 30.
Ausführlich zeigt das die Tabelle, deren Zeilen „noch nicht in anderer Reihenfolge vorhanden“ hier nicht relevant ist.

1. Bild B_1
2. Bild B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x x x
1. Bild B_2
2. Bild B_1 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x x
1. Bild B_3
2. Bild B_1 B_2 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x
1. Bild B_4
2. Bild B_1 B_2 B_3 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x
1. Bild B_5
2. Bild B_1 B_2 B_3 B_4 B_6
noch nicht in anderer Reihenfolge vorhanden x
1. Bild B_6
2. Bild B_1 B_2 B_3 B_4 B_5
noch nicht in anderer Reihenfolge vorhanden

Variationen mit Wiederholungen

Betrachtest Du dagegen Variationen aus k von n Elementen der Grundmenge mit Wiederholungen, werden also die beim ersten Durchgang entnommenen Elemente wieder zurückgelegt, so gibt es jetzt identische Elemente. Das beim ersten Durchgang entnommene Element könnte schließlich auch beim zweiten Durchgang gezogen werden. Bei jedem der k Entnahmen aus der Grundmenge könnte jetzt jedes der n Elemente ausgewählt werden.
Daher ist die Anzahl unterschiedlicher Variationen von k aus n Elementen mit

    \begin{equation*} n^k \end{equation*}

gegeben.

Beim Bilderbeispiel etwa erhältst Du demnach eins von den sechs Bildern, notierst welches es war, gibst es zurück und erhältst ein zweites Bild. Es kann dann auch vorkommen, dass Du zweimal das gleiche Bild erhältst; es gibt also jetzt 6^2=36 mögliche Variationen.

Ausführlich erkennst Du das an der Tabelle: Da das erste Bild wieder zurückgelegt wird, gibt es jetzt für das zweite Bild ebenfalls jeweils 6 Möglichkeiten:

1. Bild B_1
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x x x x
1. Bild B_2
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x x x
1. Bild B_3
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x x
1. Bild B_4
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x x
1. Bild B_5
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x x
1. Bild B_6
2. Bild B_1 B_2 B_3 B_4 B_5 B_6
noch nicht in anderer Reihenfolge vorhanden x

Was ist eine Kombination?

Eine Kombination aus k von n Elementen der Grundmenge ist schließlich ein Teil der Grundmenge, bei der im Gegensatz zur Variation die Reihenfolge der Anordnung nicht relevant ist. Sind dabei alle Elemente voneinander unterscheidbar, spricht man von einer Kombination ohne Wiederholung. Dann beträgt die Anzahl unterschiedlicher Kombinationen von k aus n Elementen:

    \begin{equation*} \left( \begin {array} {11} n\\ k \end{array} \right) = \frac {n! } { (n-k)!\cdot k!} \end{equation*}

Oben in der Tabelle der Variation ohne Wiederholung sind die möglichen Anordnungen von 2 aus 6 Bildern dementsprechend aufgeführt. In einer dritten Zeile siehst Du zudem angegeben, ob diese Kombination von Bildern noch nicht in anderer Reihenfolge aufgeführt war. Die Anzahl der „x“ beträgt folglich 15, denn

    \begin{equation*} \left( \begin {array} {11} 6\\ 2 \end{array} \right) = \frac {6! } { 2!\cdot 4!} = \frac {6 \cdot 5 } { 1 \cdot 2 } = 15 \end{equation*}

Kombination mit Wiederholungen

Betrachtest Du indes Kombinationen mit Wiederholungen aus k von n Elementen der Grundmenge, so ist die Reihenfolge der Elementanordnung irrelevant, aber es gibt identische Elemente. Beim Bilderbeispiel gibst Du bespielsweise das in der ersten Runde erhaltene Bild zurück und erhältst ein zweites Mal ein Bild ausgeteilt. In beiden Runden könnte jetzt also theoretisch jedes Bild ausgegeben werden.

Aus den oben in der Tabelle aufgeführten Variationen mit Wiederholungen sind dann nur noch solche Anordnungen relevant, die nicht schon in anderer Reihenfolge beobachtet wurden. Weiterhin sind diese  Variationen in der jeweils dritten Reihe mit einem „x“ gekennzeichnet. Ihre Anzahl beträgt 21.
Allgemein ergibt sich die Anzahl der Kombinationen von k aus n Elementen mit Wiederholungen zu

    \begin{equation*} \left( \begin {array} {11} {n+k-1}\\ k \end{array} \right) = \frac {(n+k-1)! } { k! \cdot (n-1)!} \end{equation*}

Für Dein Beispiel erhältst Du folglich

    \begin{equation*} \left( \begin {array} {11} {6+2-1}\\ 2 \end{array} \right) = \frac {(7)! } { 2! \cdot 5!} = 21 \end{equation*}

mögliche Anordnungen.

Die Tabelle stellt Dir schließlich die jeweils möglichen Anzahlen von Permutationen, Variationen und Kombinationen mit und ohne Wiederholungen gegenüber:

ohne Wiederholungen mit Wiederholungen
Permutation
alle Elemente der Grundmenge werden entnommen, das heißt k=n		 n! \frac {n!} {n_1! \cdot n_2!\cdot ... \cdot n_s!}
Variation
es werden k < n Elemente aus der Grundmenge entnommen, wobei die Reihenfolge der Entnahme relevant ist		 \frac {n! } { (n-k)!} n^k
Kombination
es werden k < n Elemente aus der Grundmenge entnommen, ohne dass die Reihenfolge der Entnahme von Bedeutung ist		 \left( \begin {array} {11} n\\ k \end{array} \right) \left( \begin {array} {11} {n+k-1}\\ k \end{array} \right)