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

  • Please login for access. Login

  • Please login for access. 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?

In einem früheren Beispiel hatten wir die Anzahl Podest-Besetzungen berechnet, die 20 Teilnehmer bilden können. Nun ist die Sache sehr sehr ähnlich, aber die Reihenfolge spielt keine Rolle mehr. Die ersten Drei sind qualifiziert und wir unterscheiden nicht, wer jetzt Erster, wer Zweiter war etc.

Es handelt sich deshalb um eine Kombination, d.h. ohne Berücksichtigung der Reihenfolge. Da die Athleten nicht doppelt vorkommen können, ist es ein “Ziehen ohne Zurücklegen”. Die Anzahl möglicher Dreierteams-Kombinationen ist deshalb:

\[ ^{20}C_3 = \frac{20!}{(20-3)! \; 3!} = \underline{1’140} \] 

Beachte, dass die Anzahl Podest-Besetzungen 6’840 betragen hat. Das ist genau das Sechsfache von 1’140. Das ist kein Zufall, denn die drei qualifizierten Athleten können auf 6 verschiedene Arten auf dem Podest stehen. Es sind wieder einmal unsere 6 Permutationen von 3 Objekten.

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?

Bevor wir uns ans Rechnen machen, unterscheiden wir drei mögliche Kategorien von Gruppen: Gruppen mit 5 Jungs, Gruppen mit 4 Jungs und Gruppen mit 3 Jungs.

Jetzt überlegen wir uns, wie wir Gruppen von 5 Jungs aus 8 Jungs bilden können. Die Reihenfolge spielt keine Rolle (Kombination) und es ist ein Ziehen ohne Zurücklegen, da jeder Schüler nur einmal in der Gruppe vorkommen kann.

\[ ^8C_5 = \frac{8!}{(8-5)! \; 5!} = 56 \]

Für die Gruppen mit 4 Jungs und einem Mädchen haben wir die Anzahl Möglichkeiten 4 aus 8 (\(^8C_4\)) bei den Jungs und die Anzahl Möglichkeiten 1 aus 7 (\(^7C_1\)) bei den Mädchen. Die beiden Kombinationszahlen müssen gemäss Fundamentalsatz der Kombinatorik mit einander multipliziert werden:

\[ ^8C_4 \;\cdot\; ^7C_1 = \frac{8!}{(8-4)! \; 4!} \cdot \frac{7!}{(7-1)! \; 1!} = 70 \cdot 7 = 490 \]

Analog berechnen wir die Anzahl Möglichkeiten für die Gruppe mit 3 Jungs und 2 Mädchen:

\[ ^8C_3 \;\cdot\; ^7C_2 = \frac{8!}{(8-3)! \; 3!} \cdot \frac{7!}{(7-2)! \; 2!} = 56 \cdot 21 = 1’176 \]

Damit hat der Lehrer total 56 + 490 + 1’176 = 1’722 Möglichkeiten, seine Fünfergruppe zusammenzustellen!

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?

Es werden 5 Karten aus 52 gezogen. Wir stellen uns die erste Frage zur Reihenfolge. Hier spielt die Reihenfolge keine Rolle, denn es kommt nicht darauf an, ob ich ein Ass mit der ersten Karte erhalten oder erst mit der Fünften. Die Reihenfolge spielt keine Rolle und wir beschränken uns auf die Kombinationen in der rechten Spalte.

Können Karten zweimal vorkommen? Werden sie gezogen und dann zurückgelegt, bevor sie nochmals gezogen werden? Nein, natürlich nicht. Wir haben hier eine Kombination ohne Zurücklegen, d.h. wir schauen uns den Quadranten rechts oben an.

\[ ^nC_k = \begin{pmatrix} n \\ k \end{pmatrix} \]

Jetzt berechnen wir einfach die Anzahl Kombinationen ohne Zurücklegen:

\[ ^{52}C_5 = \begin{pmatrix} 52 \\ 5 \end{pmatrix} = \frac{52!}{(52-5)!\;5!} = \underline{2’598’960} \]

Es gibt rund 3 Millionen verschiedene Fünfersets.

Für die Berechnung der speziellen Fünfersets mit genau 3 Assen, rechnen wir in zwei Schritten. Zuerst brauchen wir die Anzahl Kombinationen, 3 Asse aus total 4 Assen zu kriegen:

\[ ^4C_3 = \begin{pmatrix} 4 \\ 3 \end{pmatrix} = 4 \]

Das sind natürlich nur 4 Möglichkeiten, denn es gibt 4 verschiedene Asse, die im Dreierset fehlen können. Nun brauchen wir die Anzahl Kombinationen dafür, zwei Karten aus den verbleibenden 48 Karten zu ziehen:

\[ ^{48}C_2 = \begin{pmatrix} 48 \\ 2 \end{pmatrix} = 1’128 \]

Warum 48 verbleibende Karten? Nun, wir haben 3 Asse gezogen und möchten jetzt nochmals 2 Karten ziehen, die aber kein Ass sein dürfen. Wir nehmen deshalb das vierte Ass aus dem Spiel, so dass wir nur noch 52-3-1=48 Karten haben.

Gemäss Fundamentalprinzip der Kombinatorik multiplizieren wir die 3-Ass-Kombinationen mit den 2-Nichtass-Kombinationen und erhalten:

\[ ^4C_3 \;\cdot\; ^{48}C_2 \;=\; 4 \cdot 1’128 \;=\; \underline{4’512} \]

Das zweite Resultat ist rund 0.17% vom ersten Resultat, d.h. von allen möglichen Fünfersets, die die Spieler erhalten, steht die Chance genau 3 Assen zu haben bei rund 0.17% der Fälle.

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||E
1X X||
2X|X|
3X||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”
1X X | |
2X | X |
3X | | 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?

Im Extremfall könnte das erste Kind alle sieben Bonbons kriegen. Dann gibt es die Möglichkeit (ebenfalls noch extrem), dass das erste Kind sechs Bonbons hat und das zweite Kind nur eines. Wenn wir das in einer Tabelle mit Kreuzen und Trennstrichen aufzeichnen, wäre der Anfang der Tabelle wie folgt:

1|2|3
1X X X X X X X||
2X X X X X X|X|
3X X X X X X||X

Wir brauchen die Tabelle nicht vollständig aufzuzeichnen, denn wir können bereits jetzt vermuten, dass sie sehr lang sein könnte. Andererseits können wir das Problem jetzt gleich lösen, wie damals mit den 2 Kugeln Eis aus einer Auswahl von 3 Eissorten.

Die Anzahl Kombinationen von \(k\) aus \(n\) mit Zurücklegen, d.h. mit erlaubter Wiederholung, haben wir hier klar gegeben. \(n=3\) ist die Anzahl Spalten, also Kinder, die Bonbons erhalten. \(k=7\) ist die Anzahl Kreuze, also Anzahl Bonbons, die zu verteilen sind und die Anzahl Trennstriche ist wieder \(3-1=2\), eines weniger als die Anzahl Spalten. Damit können wir die Anzahl Kombinationen berechnen:

\[ \overline{^3C_7} = \frac{(3+7-1)!}{(3-1)! \; 7!} = \frac{9!}{2! \; 7!} = \underline{36} \]

Unsere vollständige Tabelle hätte 36 Zeilen gehabt!

Aufgabensammlung

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 3

    3 Teilaufgaben (pdf/Video-Lösung):
    Flugverbindungen in Europa (Textaufgabe)

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 4

    4 Teilaufgaben (pdf/Video-Lösung):
    Anwendung der Kombinationen in der Geometrie

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 5

    3 Teilaufgaben (pdf/Video-Lösung):
    Dekoration von Donuts (Textaufgabe)

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 6

    3 Teilaufgaben (pdf/Video-Lösung):
    Pralinenschachtel (Textaufgabe)

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 7

    4 Teilaufgaben (pdf/Video-Lösung):
    Anspruchsvoll: Organisation Volleyball-Turnier (Textaufgabe)

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)

Kurs
Please login for access. Login
Please login for access. Login

Lernziel in dieser Lektion

Überprüfe hier dein Gelerntes. In dieser Lektion solltest das folgende Lernziel erfüllt haben:

  • Du weisst, wie du mit multiplen Umrechnungen umgehen musst und kannst sie nacheinander ausführen. Du wendest dabei die Methode der ”Brüche mit Einheiten” an.