Das Wichtigste in Kürze
Kombinationen sind in der Kombinatorik die Anzahl Möglichkeiten, \(k\) Objekte aus einer Grundmenge \(n\) auszuwählen. Die Kombinationen sind wie k-Permutationen (Variationen), jedoch ohne Berücksichtigung der Reihenfolge.
Die Anzahl Kombinationen ohne Zurücklegen, d.h. ohne Wiederholung der Objekte, beträgt:
\[ ^nC_k = \frac{n!}{(n-k)! \; k!} = \begin{pmatrix} n \\ k \end{pmatrix} \]
Dabei haben wir für die zweite Schreibweise (rechts) den Binomialkoeffizienten verwendet.
Wenn sich die Objekte wiederholen dürfen, ist die Anzahl Kombinationen mit Zurücklegen:
\[ \overline{^nC_k} = \frac{(n+k-1)!}{(n-1)! \; k!} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \]
Hack
Lerne ein paar einleuchtende Beispiele auswendig. Sobald du auf eine neue Aufgabe triffst, vergleichst du mit den Beispielen, die du kennst und suchst nach Parallelen.
Bei Kombinationen mit Wiederholung ist es möglich, eine Auswahl von z.B. 7 Objekten aus einer Grundmenge von nur 3 Elementen zu haben, d.h. in welchen gilt:
\[ ^n C_k \qquad k > n \]
Beispielsweise können drei Kinder sieben Bonbons untereinander aufteilen, d.h. “7 aus 3” ist möglich, weil bei der Verteilung Wiederholungen möglich sind:
\[ ^3 C_7 = \begin{pmatrix} 3+7-1 \\ 7 \end{pmatrix} = \begin{pmatrix} 9 \\ 7 \end{pmatrix} \]
Video
-
TUTORIAL Videos nur für Mitglieder im Hacker-Club Login -
TUTORIAL Videos nur für Mitglieder im Hacker-Club Login
“Kombinationen sind deshalb immer weniger zahlreich als k-Permutationen mit gleichen Parameter.
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} \]
Beispiel: Qualifikationsrennen
An einem regionalen Rennen, an welchem 20 Athleten teilnehmen, können sich die drei Besten für die landesweiten Wettkämpfe qualifizieren. Wie viele mögliche Dreierteams gibt es?
Beispiel: Gruppenbildung
Während der Projektwoche braucht der Lehrer eine Gruppe von 5 Schülerinnen und Schülern, die zusammen die schweren Sachen wegräumen. In der Gruppe sollten mindestens 3 Schüler sein.
Auf wie viele Arten kann er diese Gruppe zusammenstellen, wenn in der Klasse 8 Jungs und 7 Mädchen sind?
Beispiel: Spielkarten
Ein französisches Kartenset hat total 52 Karten mit 4 Farbwerten. Den Spielern werden 5 zufällige Karten verteilt. Wie viele verschiedene Fünfersets sind überhaupt möglich? Wie viele Fünfersets enthalten genau 3 Assen?
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.
Beispiel: 7 Bonbons für 3 Kinder
Drei Kinder spielen ein Spiel, wobei der Gewinner oder die Gewinnerin jeder Runde, ein Bonbon aus der Schale nehmen darf. In der Schale hat es noch 7 Bonbons für die letzten 7 Runden des Spiels.
Auf wie viele Arten können die 7 verbleibenden Bonbons auf die drei Kinder verteilt werden?
Aufgabensammlung
Lernziele
- Du weisst, inwiefern sich eine Kombination von einer Permutation bzw. k-Permutation unterscheidet.
- Du kannst die Anzahl Kombinationen mit oder ohne Zurücklegen berechnen.
Weitere Links
Kombination (Wikipedia)
publiziert:
überarbeitet:
publiziert:
überarbeitet:
Schreib deine Frage / Kommentar hier unten rein. Ich werde sie beantworten.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.