✖

Variationen

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

Wir verwenden Variationen, wenn wir eine bestimmte Anzahl von Objekten aus einer Menge von Objekten auswählen, und die Reihenfolge, in der wir diese Objekte auswählen, ist wichtig.

Ableitung einer Formel

Beginnen wir mit einem typischen Variationsproblem: Im Dorf findet jährlich ein Wettbewerb im Pflaumenknödelessen statt. Insgesamt sieben fettige Teilnehmer kommen in die Endrunde. Berechnen Sie, wie viele Möglichkeiten es insgesamt für diese sieben Teilnehmer gibt, die ersten drei Plätze zu belegen.

Es ist wichtig zu beachten, dass es in diesem Beispiel auf die Reihenfolge ankommt. Wenn wir zum Beispiel wissen, dass Tonda, Matěj und Koloděj die ersten drei Plätze belegen werden, dann gibt es für dieses Trio insgesamt sechs verschiedene Platzierungen:

  • Tonda, Matěj, Koloděj;
  • Tonda, Kolodej, Matěj;
  • Matěj, Tonda, Koloděj;
  • Matěj, Koloděj, Tonda;
  • Koloděj, Tonda, Matěj;
  • Koloděj, Matěj, Tonda.

Das sind alles verschiedene Platzierungen, und wir wollen berechnen, wie viele verschiedene Platzierungen wir zusammenstellen können, wenn es 7 Konkurrenten gibt.

Wir verwenden dazu die kombinatorische Produktregel. Nehmen wir an, wir wählen Dreiergruppen der Form [x1, x2, x3], wobei x1 der Fahrer ist, der als Erster ins Ziel gekommen ist, usw. Welche Rennfahrer können wir nach x1 setzen? Alle, also können wir 7 Fahrer nach x1 einordnen. Welche können wir nach x2 einfügen? Alle, außer dem, den wir bereits auf den ersten Platz gesetzt haben, also können wir 7 − 1 = 6 hinter x2 setzen. Dann können wir die Teilnehmer, die nicht auf dem ersten oder zweiten Platz sind, hinter x3 setzen, so dass wir 7 − 2 = 5 Optionen haben. Wir wenden die kombinatorische Produktregel an und erhalten die Gesamtzahl der Möglichkeiten: 7 · 6 · 5 = 210.

Wir können feststellen, dass wir, wenn wir die Anzahl aller Möglichkeiten auf den ersten 4 Plätzen wissen wollen, 7 − 3 = 4 hinter x4 setzen können, so dass die Gesamtzahl der Möglichkeiten 7 · 6 · 5 · 4 = 840 ist. Was können wir daraus ableiten?

Wenn wir eine Menge von n Elementen haben (7 Esser im Beispiel hier) und wir wählen 3 Elemente aus, ist das Ergebnis je nach Reihenfolge gleich n · (n − 1) · (n − 2). Alle können an erster Stelle stehen, einer weniger an nächster Stelle und so weiter. Daraus lässt sich eine allgemeine Formel für die Auswahl von k Elementen aus einer Menge von n Elementen ableiten: Die Anzahl der Möglichkeiten ist gleich n · (n − 1) · (n − 2) · … · (n − k + 1).

Wir modifizieren diese Formel noch weiter, indem wir eine Fakultät verwenden. Wenn wir uns anschauen, wie die Fakultät von sieben aussieht: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 und wie wir die Anzahl aller Medaillenplatzierungen gezählt haben 7 · 6 · 5, sehen wir eine gewisse Ähnlichkeit. Wir müssen nur das Ende weglassen, d. h. wir müssen 7! durch 4 · 3 · 2 · 1 dividieren, dann bleibt nur noch 7 · 6 · 5 übrig. Und was ist der Ausdruck 4 · 3 · 2 · 1 gleich? Er ist gleich 4!.

Wir können also schreiben, dass wir, wenn wir eine Menge von n Elementen haben und insgesamt k Elemente auswählen, abhängig von der Reihenfolge, insgesamt

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

Möglichkeiten. Wenn wir die Zahlen aus dem Pflaumenrennen in diese Formel einsetzen:

$$ V(3, 7) = \frac{7!}{(7-3)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210. $$

Computer

Der folgende Rechner berechnet die Anzahl der Varianten für eine gegebene n und k, einschließlich des Verfahrens.

k:n:

Gelöste Beispiele

  1. Bleiben wir bei dem Knödelwettessen. Wie würde sich die Anzahl der möglichen Medaillenplatzierungen ändern, wenn wir wüssten, dass Ludva Schnitzell, die ein Macho ist und immer gewinnt, zum Rennen kommt? D.h. wie viele verschiedene Medaillenplatzierungen gibt es, wenn wir 7 Teilnehmer haben und Ludva sicher gewinnt?

Auch hier handelt es sich um eine einfache Variante: Der erste Platz ist sicher, und von den verbleibenden 6 Wettbewerbern müssen wir bestimmen, wie sie den zweiten und dritten Platz besetzen können. Wir wählen also 2 Elemente aus der Menge der 6 Elemente aus, was zu einer Variante führt

$$ V(2, 6) = \frac{6!}{(6-2)!}=30 $$

  1. Früher, als Ludva Schnitzell noch keine große Nummer war, kam sie regelmäßig unter die ersten drei. Wie viele verschiedene Medaillenplatzierungen gibt es, wenn wir 7 Teilnehmer haben und Ludva sicher eine Medaille bekommt?

    Dieses Beispiel unterscheidet sich von dem vorherigen dadurch, dass wir nicht wissen, wo Ludva sich platziert hat; er könnte auch Zweiter oder sogar Dritter geworden sein, wofür er sich immer noch schämt. Daher müssen wir insgesamt drei verschiedene Varianten berechnen: wenn Ludva gewonnen hätte, dann wenn Ludva eine Silbermedaille und schließlich eine Bronzemedaille erreicht hätte. Natürlich gibt es jedes Mal nur noch zwei Plätze, auf denen sich jemand anderes platzieren kann. Wenn Ludva zum Beispiel Zweite geworden wäre, hätten die anderen Teilnehmer entweder den ersten oder den dritten Platz belegen können. Wir zählen also wieder die Zwei-Personen-Variante von sechs, nur müssen wir sie dreimal zählen, für drei verschiedene Platzierungen von Ludva. Die Anzahl aller Platzierungen ist also gleich:

    $$ 3 \cdot V(2, 6) = 3 \cdot \frac{6!}{(6-2)!} = 3 \cdot 30 = 90 $$

    Beachten Sie, dass wir die drei vor der Variation als V(1, 3) schreiben können, weil wir tatsächlich ein Element (eine bestimmte Platzierung) aus einer Menge von drei Elementen (drei Medaillenpositionen) auswählen.

  2. An der Schule gibt es insgesamt 20 Lehrer. Die Abschlussfeier steht kurz bevor und wir müssen einen Ausschuss mit folgender Zusammensetzung bilden: ein Vorsitzender, ein guter Vorsitzender und ein schlechter Vorsitzender. Wie viele Möglichkeiten gibt es insgesamt?

    Die erste Frage, die wir beantworten müssen, ist, ob die Reihenfolge eine Rolle spielt - ja, sie spielt eine Rolle, denn wir können die drei Lehrer auf sechs verschiedene Arten neu zusammenstellen. Jetzt ist es einfach - wir wählen eine 3-Personen-Variante aus 20 Elementen:

    $$ V(3, 20) = \frac{20!}{17!}=6840. $$

  3. Wie viele dreistellige Zahlen können wir aus den Ziffern {0, 1, 2, 3, 4, 5} zusammenstellen, wenn sich keine Ziffer wiederholen kann?

    Spielt die Reihenfolge eine Rolle? Ja, es kommt darauf an, 123 ist eine andere Zahl als 321. Wie viele verschiedene Drillinge gibt es? Das ist eine einfache dreistellige Variante von 6:

    $$ V(3, 6) = \frac{6!}{3!}=120. $$

    Aber wir müssen noch die Varianten abziehen, die von vornherein eine Null haben, denn 012 ist keine dreistellige Zahl. Die Frage ist nun: Wie viele verschiedene Dreiergruppen gibt es, die mit einer Null beginnen? In diesem Fall wechseln sich nur die Ziffern an den beiden verbleibenden Stellen ab (die Dreiergruppen haben die Form [0, x2, x3]). Wir wollen also sehen, wie viele verschiedene Paare wir mit den Zahlen {1, 2, 3, 4, 5} bilden können. Auch das ist einfach: V(2, 5) = 5!/3! = 20. Es gibt also 20 Dreierpaare, die mit Null beginnen.

    Die Gesamtzahl der dreistelligen Zahlen, die sich aus den Ziffern {0, 1, 2, 3, 4, 5} zusammensetzen, ist also 120 − 20 = 100.

  4. Wie viele verschiedene dreistellige Zahlen können wir aus den Ziffern {1, 2, 3, 4, 5} konstruieren, wenn sich keine Ziffer wiederholen darf und die resultierende Zahl ungerade sein soll?

    Die Reihenfolge ist wichtig, denn 123 ist eine andere Zahl als 321. Wir setzen eine dreistellige Zahl zusammen, die ungerade ist, d. h. die ersten beiden Stellen können eine beliebige Ziffer enthalten, aber die letzte Stelle muss eine der Ziffern {1, 3, 5} enthalten. Zunächst zählen wir die Anzahl aller Drillinge, die wir aus fünf Ziffern zusammensetzen können: V(3, 5) = 5! / 2! = 60.

    Jede Ziffer erscheint an der letzten Stelle gleich oft, d. h. bei fünf Ziffern erscheint jede Ziffer an der letzten Stelle 60 / 5 = 12. Wir haben drei Ziffern {1, 3, 5}, die an der letzten Stelle erscheinen können, also haben wir 12 verschiedene Zahlen, die auf 1 enden, 12 Zahlen, die auf 3 enden und 12 Zahlen, die auf 5 enden. Wir wenden die kombinatorische Summenregel an und erhalten eine Gesamtzahl von 12 + 12 + 12 = 36 Möglichkeiten.

  5. Berechne x, wenn du weißt, dass V(2, x) = 72. Mit anderen Worten: Wir wählen Paare aus einer Menge der Größe x und wissen, dass wir insgesamt 72 verschiedene Paare wählen können. Wie groß war die Menge, aus der wir die Paare ausgewählt haben? Schlüsseln wir es auf:

    $$ V(2, x) = \frac{x!}{(x-2)!} = 72 $$

    Als nächstes modifizieren wir:

    $$\begin{eqnarray} \frac{x!}{(x-2)!} &=& 72\\ \frac{x \cdot (x-1)\cdot(x-2)!}{(x-2)!} &=& 72 \\ x \cdot (x-1) &=&72\\ x^2-x&=&72\\ x^2-x-72&=&0 \end{eqnarray}$$

    Dies ist bereits eine klassische quadratische Gleichung, also lösen wir sie mit Hilfe einer Diskriminante oder wir schreiben die Gleichung um in die Form

    $$ (x+8)\cdot(x-9)=0 $$

    umschreiben, aus der wir bereits die Lösung ablesen können: x1 = −8 und x2 = 9. Die negative Lösung ist uns egal, da die Menge nicht negativ sein kann. Die Lösung der ursprünglichen Gleichung ist also x = 9, die Menge hatte neun Elemente.

Quellen und weiterführende Literatur