k-Permutationen (Variationen)

Im deutschsprachigen Raum werden -Permutationen meistens Variationen genannt. Dieser neue Begriff kann verwirren. In der angelsächsischen Literatur gibt des den Begriff der Variation nicht. Vielmehr wird von -Permutationen gesprochen, was ich eigentlich auch sinnvoller finde, denn es handelt sich bei Variationen wirklich nur um Teil-Permutationen von Objekten aus der Grundmenge .

Wie bei den Permutationen behalten wir bei den -Permutationen die Reihenfolge, d.h. wir unterscheiden beispielsweise zwischen und .

k-Permutation mit Zurücklegen

Ein Zahlenschloss hat 4 Ziffern. Wie lange hätte ein Dieb, wenn er sämtliche Möglichkeiten ausprobieren müsste und er für jede Einstellung 10 Sekunden Zeit bräuchte?

Eigentlich haben wir hier etwas wie ein Urnenmodell mit Zurücklegen. In der Urne haben wir zehn Kugeln mit den zehn möglichen Ziffern 0 bis 9. Für die erste Ziffer unserer Kombination ziehen wir eine Kugel. Dazu gibt es 10 Möglichkeiten oder in unserem Baumdiagramm: 10 Hauptäste.

Wir legen die Ziffer zurück, denn die gezogene Ziffer soll ja auch weiterhin noch möglich sein. Sie darf mehrmals vorkommen. Wieder ziehen wir eine Ziffer und dafür gibt es wieder 10 mögliche Ergebnisse. Da wir insgesamt vier Mal ziehen, ist die Zahl aller Möglichkeiten:

Somit braucht der Dieb 100’000 Sekunden, was rund 27.8 Stunden entspricht.

Beachte: Wir setzen einen Querbalken, um auf die mögliche Wiederholung durch Zurücklegen hinzuweisen.

k-Permutation ohne Zurücklegen

Bei einem Rennen nehmen 20 Athleten teil. Für die drei besten Sportler gibt es dann die Gold-, Silber- und Bronze-Medaille. Wie viele Podestbesetzungen sind möglich?

Wir erkennen hier ein Urnenmodell ohne Zurücklegen, denn die Athleten können nicht mehrfach durchs Ziel laufen oder mehrfach auf dem Podest stehen. Die Funktion des Ziels ist es, drei Sportler aus dem Pool der Teilnehmer zu ziehen. Weil wir eine Teilmenge aus einer Grundmenge betrachten und ihre Reihenfolge berücksichtigen, haben wir eine k-Permutation.

Für den ersten Athleten haben wir Teilnehmer zur Wahl. Für den zweiten sind es noch und für den Dritten noch . Wir verknüpfen die Möglichkeiten mit dem Produkt gemäss Fundamentalprinzip der Kombinatorik und erhalten so für die möglichen Podest-Besetzungen:

Wenn es darum ginge, alle drei Medaillen korrekt voraus zu sagen, müsste man aus den 6’840 möglichen -Permutationen die eine Richtige gewählt haben!

Jetzt können wir verallgemeinern. Die Anzahl k-Permutationen von Objekten aus einer Grundmenge Objekte errechnet sich als:

Dieses Produkt von insgesamt k-Faktoren lässt sich auch als Bruch schreiben:

Wir überprüfen kurz, ob wir für das obige Beispiel () das gleiche Resultat erhalten:

Zähler und Nenner werden unglaublich gross, aber das Resultat stimmt überein.

Beachte, dass wenn bzw. so viele Objekte gezogen werden, wie es in der Grundmenge hat, so wird aus der -Permutation eine normale -Permutation. Die Anzahl -Permutationen ist dann:

Wir sehen, dass wir das gleiche Resultat erhalten, wie für die «normale» -Permutation.

Die spezielle Null-Fakultät ist tatsächlich eins:

Wir können uns davon überzeugen, indem wir folgende Beispiele zur Hand nehmen:

oder allgemein:

Wenn wir jetzt setzen, erhalten wir:

Aus diesem Grund merken wir uns: