Kombinationen

Kombinationen verwenden wir, wenn wir aus einer Menge von Objekten eine bestimmte Anzahl von Objekten auswählen und es dabei nicht auf die Reihenfolge ankommt, in der wir diese Objekte auswählen. Eine typische Aufgabe ist das Lotto – in der Urne haben wir 49 Zahlen und ziehen daraus 6 Zahlen, wobei es egal ist, in welcher Reihenfolge wir sie ziehen.

Herleitung der Formel

Glücksrad

Gegeben sei eine Menge M, zum Beispiel M = {a; b; c; d; e}. Dann ist eine Kombination von k Elementen eine Teilmenge K ⊆ M, die genau k Elemente enthält. Weil K eine Menge ist, kommt es selbstverständlich nicht auf die Reihenfolge an. Eine Kombination von 3 Elementen aus der Menge M könnte also {a; b; d} oder {b; c; d} sein.

Der Unterschied zu den Variationen ist, dass es bei Variationen auf die Reihenfolge ankam, also sind (a, b, e) und (e, b, a) verschiedene Variationen, aber es sind dieselben Kombinationen, weil (a, b, e) und (e, b, a) dieselben Elemente enthalten; dass sie in anderer Reihenfolge stehen, interessiert uns bei Kombinationen nicht.

Wir können aber die Variationen nutzen, um die Formel für die Anzahl aller verschiedenen Kombinationen zu erhalten. Wir wissen, dass es genau

$V (k; n) = \frac{n!}{(n - k)!}$

Variationen von k aus n Elementen gibt. Würden wir also die Anzahl aller Variationen von 3 Elementen aus der vorherigen Menge M = {a; b; c; d; e} berechnen, erhielten wir V(3; 5) = 60 verschiedene Variationen. Allerdings hätten wir dort für jedes Tripel auch alle seine Permutationen. D. h. wir hätten dort das Tripel abc, aber auch die Tripel acb, bac, bca, cab und cba. Das sind sechs verschiedene Variationen, aber es ist eine Kombination, weil alle dieselben Elemente haben.

Haben wir also ein Tripel, wie viele verschiedene Permutationen dieses Tripels gibt es? Genau 3!. Mit anderen Worten: Es gibt genau 3!-mal mehr Variationen von 3 Elementen als Kombinationen von 3 Elementen. Statt mit einer Kombination zu rechnen, rechnen wir mit 3! Variationen mehr, mit jeder Permutation des gegebenen Tripels. Teilen wir also die Anzahl der Variationen durch 3!, erhalten wir die Anzahl der Kombinationen.

Das bisherige Vorgehen können wir verallgemeinern und sagen: Suchen wir die Anzahl aller verschiedenen Kombinationen von k Elementen aus einer Menge der Größe n, so ist diese Anzahl, die wir mit C(k; n) bezeichnen, gleich

$C (k; n) = \frac{V (k; n)}{k!},$

d. h. die Anzahl der Variationen geteilt durch k!, was die Anzahl der Permutationen jedes k-Tupels ist. Die Formel können wir umformen, indem wir die Formel für die Berechnung der Variationen ausschreiben:

$C (k; n) = \frac{V (k; n)}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Beispiel: Die Anzahl der Kombinationen von 2 Elementen aus der Menge {a; b; c} ist

$C (2; 3) = \frac{3!}{1! \cdot 2!} = 3$

und es sind diese Kombinationen: {a; b}, {a; c} und {b; c}. Bei den Kombinationen von 3 Elementen aus der ursprünglichen Menge M = {a; b; c; d; e} bekämen wir die Anzahl

$C (3; 5) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

und es sind diese Kombinationen: {a; b; c}, {a; b; d}, {a; b; e}, {a; c; d}, {a; c; e}, {a; d; e}, {b; c; d}, {b; c; e}, {b; d; e}, {c; d; e}.

Binomialkoeffizient

Die bisherige Schreibweise der Formel mit C(k; n) wird kaum verwendet, stattdessen verwendet man den sogenannten Binomialkoeffizienten. Der Binomialkoeffizient hat diese Form

$(\binom{n}{k})$

es ist gewissermaßen ein Bruch ohne Bruchstrich (den du aber aus Gewohnheit trotzdem schreiben wirst), dafür mit Klammern (die sind nicht optional, die müssen dort stehen). Den Binomialkoeffizienten lesen wir „n über k“. Der Wert des Binomialkoeffizienten ist dann gleich C(k; n).

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Haben wir also eine Menge mit 5 Elementen und wählen daraus Vierergruppen aus, so ist ihre Gesamtzahl

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Grundlegende Beziehungen

Für den Binomialkoeffizienten und n ∈ ℕ gilt:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Weiter gilt für n, k ∈ ℕ₀ und k ≤ n

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Und für n, k ∈ ℕ₀ und k < n gilt

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Rechner

Der folgende Rechner berechnet dir den Binomialkoeffizienten n über k.

Gelöste Beispiele

Beginnen wir mit dem bereits erwähnten Lotto. Dabei werden aus einer Urne mit 49 Kugeln insgesamt 6 Kugeln gezogen. Wie viele verschiedene Ziehungen sind möglich?

Zuallererst – kommt es auf die Reihenfolge beim Ziehen der Zahlen an? Nein, wir tippen nur die Zahlen, nicht ihre Reihenfolge. Wir verwenden Kombinationen. Wir haben insgesamt 49 Kugeln, ziehen 6 Kugeln, und erhalten den Binomialkoeffizienten

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Es gibt insgesamt 13.983.816 mögliche Ziehungen. Das ergibt übrigens die Wahrscheinlichkeit eines Gewinns bei einem Tipp 1/13.983.816, das sind 0,00000715112 %.
Max, ein bekannter Herzensbrecher, ist gerade auf einem Dorffest, auf dem es insgesamt 13 hübsche Mädchen gibt, an denen er Interesse hätte. Max weiß, dass er an einem Abend 4 verschiedene Mädchen glücklich machen kann. Aus wie vielen verschiedenen Vierergruppen kann Max wählen?

Das ist wieder ein einfaches Beispiel zu Kombinationen, auf die Reihenfolge kommt es nicht an, Max wird bei der ersten Dame genauso gut sein wie bei der letzten. Wir erhalten also eine Menge von 13 Mädchen, aus denen wir jeweils 4 Mädchen auswählen. Das führt auf den Binomialkoeffizienten

$(\binom{13}{4}) = 715.$
Du hast eine Gruppe von fünfzig Personen – die Hälfte Männer und die Hälfte Frauen. Wie viele verschiedene Dreiergruppen gibt es, wenn sie nicht nur aus einem Geschlecht bestehen dürfen (d. h. in der Dreiergruppe dürfen nicht drei Männer oder drei Frauen vorkommen).

Das ist schon eine etwas kompliziertere Kombination. Schließen wir eingeschlechtliche Dreiergruppen aus, bleiben uns nur zwei Möglichkeiten, wie die Dreiergruppe zusammengesetzt sein kann – zwei Männer und eine Frau oder ein Mann und zwei Frauen, wobei die Anzahl der Kombinationen der ersten Gruppe (zwei Männer und eine Frau) gleich der Anzahl der Kombinationen der zweiten Gruppe ist. Es genügt also, die Anzahl der Kombinationen der ersten Gruppe zu berechnen und sie anschließend mit zwei zu multiplizieren. Jetzt ist es wieder ein Kinderspiel. Wir bestimmen die Anzahl der Kombinationen verschiedener Männerpaare, das ist fünfundzwanzig über zwei, und multiplizieren sie mit der Anzahl der Kombinationen einer Frau (die ist fünfundzwanzig, siehe grundlegende Beziehungen oben, konkret die zweite Zeile). Dieses Ergebnis multiplizieren wir nur noch mit zwei und haben das Endergebnis.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
In einer Kiste sind 15 Produkte, von denen 4 defekt sind. Auf wie viele Arten lassen sich 6 Produkte so auswählen,
- dass keines defekt ist? Wir wählen jetzt 6 Produkte aus den 15 − 4 = 11 Produkten, die nicht defekt sind. Wir erhalten also den Binomialkoeffizienten
  
  $(\binom{11}{6}) = 462.$
- dass genau ein Produkt defekt ist? Wir wählen also eine Menge, die 5 funktionierende Produkte und 1 defektes enthält. Funktionierende Produkte haben wir insgesamt 11, defekte haben wir 4. Wir verwenden die Produktregel und erhalten das Ergebnis:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- dass höchstens eines defekt ist? Zur Lösung nutzen wir die vorherigen Ergebnisse. Wir wissen, dass wir insgesamt 462 Möglichkeiten haben, genau 6 funktionierende Produkte auszuwählen, und 1848 Möglichkeiten, fünf funktionierende und ein defektes Produkt auszuwählen. Wir verwenden also die Summenregel, addieren diese Ergebnisse und haben das gewünschte Ergebnis, d. h. höchstens ein defektes Produkt (= entweder kein defektes Produkt oder genau ein defektes). Das Ergebnis ist also: 462 + 1848 = 2310.

Kapitel: Kombinatorik, Variationen, Permutationen, Kombinationen, Variation mit Wiederholung, Kombination mit Wiederholung, Wie viele verschiedene PINs gibt es?

« Zurück: Permutationen

Weiter: Variation mit Wiederholung »