Kombinationen

Kombinationen: k-Permutationen ohne Reihenfolge

Bei den Permutationen und k-Permutationen haben wir bisher immer die Reihenfolge berücksichtigt. Das mussten wir fast, denn wenn wir Permutationen sind per Definition “verschiedene Reihenfolgen”.

Nehmen wir als Beispiel drei mathematische Objekte, die wir einfach \(A\), \(B\) und \(C\) nennen. Wenn es nicht mehr darauf ankommt, in welcher Reihenfolge sie stehen müssen, schrumpfen die sechs Permutationen zu einer Menge:

\[ (A,B,C),\;\; (A,C,B),\;\; (B,A,C),\;\; (B,C,A),\;\; (C,A,B),\;\; (C,B,A) \quad \rightarrow \quad \Big\{ A, B, C \Big\} \]

Kombinationen sind deshalb immer weniger zahlreich als k-Permutationen mit gleichen Parameter.

Kombinationen ohne Zurücklegen

Stellen wir uns einen Eisstand vor, der 18 leckere Eissorten im Angebot hat. Amélie wählt zwei Kugeln aus. Wie viele mögliche Eiskombinationen gibt es, wenn beide Kugeln unterschiedlich sind?

Beachte, dass in der Kombinatorik “zweimal das gleiche Eis” bedeutet, dass die gewählte erste Kugel “zurückgelegt” wird. In diesem ersten Beispiel wollen wir das nicht und verlangen, dass beide Kugeln wirklich unterschiedlich sind. Wir betrachten deshalb ein Urnenmodell ohne Zurücklegen.

Mit Reihenfolge hätten wir eine k-Permutation: “2 aus 18”, die schnell berechnet wäre:

\[ \require{cancel} ^nP_k = \frac{n!}{(n-k)!} = \frac{18!}{(18-2)!} = \frac{18!}{16!} = \frac{18 \cdot 17 \cancel{\cdot 16 \cdot 15 \cdot … \cdot 2 \cdot 1}}{\cancel{16 \cdot 15 \cdot … \cdot 2 \cdot 1}} = 18 \cdot 17 = 306 \]

In der k-Permutation wird aber die Reihenfolge unterschieden, d.h. Schokolade auf Vanille ist nicht gleich Vanille auf Schokolade.

Wir haben bei zwei Kugeln zwei mögliche \(k\)-Permutationen:

\[ (A,B), \quad (B,A) \]

Hätte Amélie drei Kugeln gewählt, dann gäbe es sechs \(k\)-Permutationen:

\[ (A,B,C),\;(A,C,B),\;(B,A,C),\;(B,C,A),\;(C,A,B),\;(C,B,A) \]

Für Amélie kommt es aber nicht darauf an, in welcher Reihenfolge der Eisverkäufer die Kugel serviert hat. Sie ignoriert die Reihenfolge und macht aus “Schokolade auf Vanille” bzw. “Vanille auf Schokolade” einfach nur einen Fall, nämlich “Schokolade und Vanille”:

\[ (A,B),\;\; (B,A) \quad \rightarrow \quad \Big\{ A, B \Big\} \]

Deshalb teilen wir 306 mögliche k-Permutationen von zwei Kugeln aus 18 Eissorten durch die Anzahl verschiedener Reihenfolgen von zwei Kugeln (2!) und erhalten die Anzahl möglicher Kombinationen:

\[ ^{18}C_2 = \frac{306}{2!} = \frac{306}{2} = 153 \]

Es gibt für Amélie 153 verschiedene Kombinationen aus den 18 Eissorten (bei zwei unterschiedlichen Kugeln).

Verallgemeinern wir diese Rechnung, so müssen wir die Anzahl k-Permutationen \(P_k^n\) noch durch die Anzahl Reihenfolgen \(k!\) teilen, um die korrekte Anzahl Kombinationen von \(k\) aus \(n\) zu erhalten:

\[ ^nC_k = \frac{P_k^n}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)! \; k!} \]

Der etwas komplizierte Bruch kann durch den sog. Binomialkoeffizienten abgekürzt geschrieben werden. Für die Anzahl Kombinationen von \(k\) Objekten aus einer Grundmenge von \(n\) Objekten ohne Zurücklegen, erhalten wir:

\[ ^nC_k = \frac{n!}{(n-k)! \; k!} = \begin{pmatrix} n \\ k \end{pmatrix} \]

Kombinationen mit Zurücklegen

Wir erlauben jetzt das Zurücklegen oder anders gesprochen: Es dürfen Wiederholungen vorkommen. Beim Beispiel des Eisstandes bedeutet das: Amélie kann die gleiche Eissorte mehrfach wählen.

Erstaunlicherweise macht das die Sache etwas komplizierter. Wir schauen uns wieder das Beispiel der zwei Kugeln Eis an, erlauben Amélie dieses Mal aber auch zweimal auf die gleiche Sorte zu setzen. Das ist das, was wir mit “Zurücklegen” der Kugel im Urnenmodell meinen. Die gleiche Sorte kann nochmals gezogen werden.

Um die Veranschaulichung dieses Beispiels übersichtlich zu behalten, reduzieren wir die zur Auswahl stehenden Eissorten (vorerst) auf drei!

Wir bauen eine kleine Tabelle auf. Horizontal haben wir die drei üblichen Eissorten Schokolade (S), Vanille (V) und Erdbeer (E). Jetzt machen wir einfach für jede mögliche Kombination eine Zeile, indem wir für die gewählte Sorte ein Kreuz setzen:

	S	|	V	|	E
1	X X	|		|
2	X	|	X	|
3	X	|		|	X
4		|	X X	|
5		|	X	|	X
6		|		|	X X

Aus der Tabelle lesen wir ab, dass es 6 mögliche Kombinationen gibt. Wären das Zurücklegen nicht erlaubt, so würden drei Kombinationen wegfallen, nämlich \(\{S,S\}\), \(\{V,V\}\) und \(\{E,E\}\). Wir kontrollieren kurz, ob wir ohne Zurücklegen tatsächlich auf 6 – 3 = 3 Kombinationen kommen:

\[ ^3C_2 = \begin{pmatrix} 3 \\ 2 \end{pmatrix} = \frac{3!}{(3-2)!\;2!} = \frac{6}{1 \cdot 2} = 3 \]

Es stimmt! Wir haben beim Modus mit Zurücklegen drei Kombinationen mit unterschiedlichen Kugeln und drei Kombinationen mit gleichen Kugeln.

Zurück zu unserer Tabelle. Ich habe sie bewusst so gezeichnet, dass die Trennstriche “|” ebenfalls vorkommen. Lass uns die sechs Zeilen nun als Code, d.h. als Permutationen von “X” und “|” aufschreiben:

	“Code”
1	X X | |
2	X | X |
3	X | | X
4	| X X |
5	| X | X
6	| | X X

Die Codes sind eigentlich 6 Permutationen mit Wiederholung aus einer Grundmenge von 4 Objekten (“Buchstaben”) mit je doppelt vorkommenden “X” und “|”:

\[ ^4P_{(2,2)} = \frac{4!}{2!\;2!} = \frac{24}{4} = 6 \]

Im oberen Fall bestanden die Permutationen aus je zwei “X” und “|”, was 4 “Buchstaben” entspricht. Allgemeiner gesprochen, ist die Grundmenge \(n=k+s\), wobei \(k\) die Anzahl Kreuze und \(s\) die Anzahl Trennstriche bedeutet.

Wir können die Anzahl möglicher Permutationen mit \(k\) Kreuzen und \(s\) Strichen, die sich wiederholen, aufschreiben als:

\[ ^{k+s}P_{(k,s)} = \frac{(k+s)!}{k!\;s!} \]

Nun ist die Anzahl Striche \(s\) eigentlich immer gleich \((n-1)\), denn wir haben \(n\) Spalten in unserer Tabelle und dazu braucht es immer \((n-1)\) Trennstriche:

\[ s = n-1\]

Wir ersetzen \(s\) mit dem neuen Ausdruck und erhalten:

\[ \overline{^nC_k} = ^{k+n-1}P_{(k,n-1)} = \frac{(k+n-1)!}{(n-1)\;k!} \]

Damit haben wir die allgemeine Formel für die Berechnung der Anzahl Kombinationen mit Zurücklegen von \(k\) Objekten aus einer Grundmenge von \(n\). Wir können sie auch mit Hilfe des Binomialkoeffizienten schreiben:

\[ \overline{^nC_k} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \]

Wie gesagt, geht es hier um Kombinationen, d.h. die Reihenfolge der gezogenen Objekte wird nicht berücksichtigt.