✖

Kombination

Kapitoly: Kombinatorik, Variationen, Permutation, Kombination, Variationen mit Wiederholungen, Kombination mit Wiederholung, Wie viele verschiedene PINs gibt es, Taschenrechner.

Wir verwenden Kombinationen, wenn wir eine bestimmte Anzahl von Objekten aus einer Menge von Objekten auswählen, und die Reihenfolge, in der wir diese Objekte auswählen, spielt keine Rolle. Ein typisches Problem ist eine Sportka - wir haben 49 Zahlen in einem Pool und wir ziehen 6 davon, egal in welcher Reihenfolge wir sie ziehen.

Die Ableitung der Formel

Glücksrad

Betrachten wir eine Menge M, zum Beispiel M = {a, b, c, d, e}. Dann ist die k-Mitgliederkombination eine Teilmenge von K ⊆ M, die nur k Elemente enthält. Da K eine Menge ist, spielt die Reihenfolge natürlich keine Rolle. Eine dreigliedrige Kombination aus der Menge M könnte also {a, b, d} oder {b, c, d} sein.

Der Unterschied zu Variationen besteht darin, dass bei Variationen die Reihenfolge eine Rolle spielt. [a, b, e] und [e, b, a] sind also verschiedene Variationen, aber sie sind dieselbe Kombination, weil [a, b, e] und [e, b, a] dieselben Elemente enthalten; dass sie in einer anderen Reihenfolge stehen, ist für uns bei Kombinationen nicht von Interesse.

Aber wir können die Variationen verwenden, um eine Formel für die Anzahl aller verschiedenen Kombinationen zu erhalten. Wir wissen, dass die k-Element-Variationen der Menge mit n -Elementen einfach sind

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

Wenn wir also die Anzahl aller dreigliedrigen Variationen aus der vorherigen Menge M = {a, b, c, d, e} zählen würden, erhielten wir V(3, 5) = 60 verschiedene Variationen. Allerdings hätten wir für jedes Tripel auch alle seine Permutationen dabei. Das heißt, wir hätten das Tripel abc, aber auch die Tripel acb, bac, bca, cab und cba. Das sind sechs verschiedene Varianten, aber es ist eine Kombination, weil sie alle die gleichen Elemente haben.

Wenn wir also ein Tripel haben, wie viele verschiedene Permutationen dieses Tripels gibt es dann? Nur 3!. Mit anderen Worten: Es gibt nur 3! mehr Variationen von drei als Kombinationen von drei. Anstatt mit einer Kombination zu rechnen, zählen wir mit jeder Permutation eines gegebenen Tripels 3! mehr Varianten. Wenn wir also die Anzahl der Permutationen durch 3! dividieren, erhalten wir die Anzahl der Kombinationen.

Wir können das vorherige Verfahren verallgemeinern und sagen, dass, wenn wir nach der Anzahl aller verschiedenen k-ary Kombinationen aus einer Menge der Größe n suchen, dann ist diese Anzahl, bezeichnet mit C(k, n), gleich,

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

d.h. die Anzahl der Variationen geteilt durch k!, das ist die Anzahl der Permutationen jedes k-Würfels. Wir können die Formel abändern, indem wir die Formel zur Berechnung der Variationen aufschlüsseln:

$$ 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 binomischen Kombinationen aus der Menge {a, b, c} ist

$$ C(2, 3) = \frac{3!}{1!\cdot2!} = 3 $$

und diese Kombinationen sind: {a, b}, {a, c} und {b, c}. Für die dreigliedrigen Kombinationen aus der ursprünglichen Menge M = {a, b, c, d, e} würden wir die Anzahl von

$$ C(3, 5) = \frac{5!}{(5-3)!\cdot3!}=10 $$

und das sind die folgenden 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}.

Die Kombinationszahl

Die bisherige Schreibweise der Formel mit C(k, n) wird nicht mehr verwendet, stattdessen wird die so genannte Kombinationszahl verwendet. Die Kombinationszahl hat die folgende Form

$$ {n \choose k} $$

Es handelt sich um eine Art Bruch ohne Bruchstrich (den Sie aus Gewohnheit ohnehin dorthin schreiben werden), aber mit Klammern (diese sind nicht optional, sondern müssen vorhanden sein). Wir lesen die Kombinationszahl als "en über ka". Der Wert der Kombinationsnummer ist dann derselbe wie C(k, n).

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

Wenn wir also eine Menge von 5 Elementen haben und daraus Quads auswählen, ist die Gesamtzahl der Elemente

$$ {5 \choose 4} = \frac{5!}{1! \cdot 4!} = 5. $$

Grundlegende Beziehungen

Für die Kombinationszahl und n ∈ ℕ gilt das Folgende:

$$\begin{eqnarray} {n \choose 0} = {n \choose n} = {0 \choose 0} &=& 1\\ {n \choose 1} &=& n \end{eqnarray}$$

Außerdem gilt für n, k ∈ ℕ0 und k ≤ n Folgendes

$$\begin{eqnarray} {n \choose n - k} &=& {n \choose k}. \end{eqnarray}$$

Und für n, k ∈ ℕ0 und k < n gilt das Folgende

$$\begin{eqnarray} {n \choose k} + {n \choose k+1} &=& {n+1 \choose k+1}. \end{eqnarray}$$

Der Rechner

Der folgende Rechner berechnet die Kombinationszahl von n über k, einschließlich des Verfahrens.

Gelöste Beispiele

  1. Beginnen wir mit dem oben erwähnten Sport. In diesem Spiel werden 6 Kugeln aus einem Pool von 49 Kugeln gezogen. Wie viele verschiedene Möglichkeiten können wir ziehen?

    Zunächst einmal - spielt die Reihenfolge des Ziehens der Zahlen eine Rolle? Es spielt keine Rolle, wir raten nur die Zahlen, nicht ihre Reihenfolge. Wir werden Kombinationen verwenden. Wir haben insgesamt 49 Kugeln, wir ziehen 6 Kugeln, wir erhalten eine Kombinationszahl

    $$ {49 \choose 6} = \frac{49!}{(49-6)!\cdot6!}=\frac{49!}{43!\cdot6!} = 13{,}983,816 $$

    Insgesamt gibt es 13.983.816 Möglichkeiten, die gezogen werden können. Daraus ergibt sich übrigens die Gewinnwahrscheinlichkeit für einen Einsatz 1/13 983 816, also 0,00000715112 %.

  2. Sagvan, ein bekannter Mädchenschwarm, befindet sich gerade auf einem Dorftanz, bei dem es insgesamt 13 schöne Mädchen gibt, an denen er interessiert wäre. Sagvan weiß, dass er in der Lage ist, 4 verschiedene Mädchen an einem Abend glücklich zu machen. Aus wie vielen verschiedenen Viererkombinationen kann Sagvan wählen?

    Dies ist wieder ein einfaches Beispiel für Kombinationen, die Reihenfolge spielt keine Rolle, Sagvan wird mit dem ersten Mädchen genauso gut sein wie mit dem letzten. Wir erhalten also eine Reihe von 13 Mädchen, von denen wir immer 4 Mädchen wählen. Dies führt zu einer Kombinationszahl

    $$ {13 \choose 4} = 715. $$

  3. Sie haben eine Gruppe von 50 Personen - zur Hälfte männlich und zur Hälfte weiblich. Wie viele verschiedene Drillinge von Personen gibt es, wenn sie nicht nur aus einem Geschlecht bestehen dürfen (d. h. es dürfen nicht drei Männer oder drei Frauen in einem Drilling sein).

    Das ist eine etwas kompliziertere Kombination. Wenn wir eingeschlechtliche Dreiergruppen von Personen ausschließen, bleiben nur zwei Möglichkeiten übrig, wie eine 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. Wir brauchen also nur die Anzahl der Kombinationen der ersten Gruppe zu berechnen und sie dann mit zwei zu multiplizieren. Jetzt ist es wieder ganz einfach. Wir bestimmen die Anzahl der Kombinationen verschiedener Männerpaare, die fünfundzwanzig über zwei beträgt, und multiplizieren diese mit der Anzahl der Kombinationen einer Frau (das macht fünfundzwanzig, siehe die vorherige Liste der Kombinationszahlen, insbesondere die allererste). Wir multiplizieren dieses Ergebnis einfach mit zwei und erhalten das Endergebnis.

    $$ 2 \cdot {25 \choose 2} \cdot {25 \choose 1} = 15000. $$

  4. Es befinden sich 15 Produkte in der Schachtel, von denen 4 fehlerhaft sind. Auf wie viele Arten können 6 Produkte so ausgewählt werden,

    • so dass keines von ihnen defekt ist? Im Moment wählen wir 6 Produkte aus 15 − 4 = 11 aus, die nicht fehlerhaft sind. Das ergibt eine Kombinationszahl

      $$ {11 \choose 6} = 462. $$

    • so dass nur ein Produkt fehlerhaft ist? Wir wählen also einen Satz aus, der 5 funktionierende Produkte und 1 defektes Produkt enthält. Wir haben 11 funktionsfähige Produkte und 4 fehlerhafte Produkte. Wir verwenden die kombinatorische Produktregel, um das Ergebnis zu erhalten:

      $$ {11 \choose 5} \cdot {4 \choose 1} = 1848 $$

    • so dass höchstens eines fehlerhaft ist? Wir verwenden die vorherigen Ergebnisse zur Lösung. Wir wissen, dass wir insgesamt 462 Möglichkeiten haben, nur 6 funktionale Produkte auszuwählen, und wir haben 1848 Möglichkeiten, 5 funktionale und 1 defektes Produkt auszuwählen. Wir verwenden also die kombinatorische Summenregel, addieren diese Ergebnisse und erhalten das gewünschte Ergebnis, d.h. höchstens ein fehlerhaftes Produkt (= entweder kein fehlerhaftes Produkt oder nur eines). Das Ergebnis ist: 462 + 1848 = 2310.

Quellen und weiterführende Literatur