Das Wichtigste in Kürze

Die k-Permutationen bilden eine der zwei Säulen der Konzepte in der Kombinatorik wenn die Reihenfolge wichtig ist. Bei Wegfall der Reihenfolge würden wir stattdessen die Kombinationen verwenden.

Kombinationen geben uns die Anzahl Möglichkeiten von \(k\) Objekten aus einer Grundmenge von \(n\) Objekten, mit Zurücklegen der Objekte nach jedem Zug:

\[ \overline{^nP_k} = n \cdot n \cdot n \cdot \;…\; \cdot n \;\;=\;\; n^k \]

Wenn wir die Wiederholungen nicht zulassen, d.h. für eine k-Permutation von \(k\) Objekten aus einer Grundmenge von \(n\) Objekten ohne Zurücklegen der Objekte, ist die Anzahl Möglichkeiten:

\[ ^nP_k = \frac{n!}{(n-k)!} \]

Die Permutationen sind ein Spezialfall der k-Permutationen, in welchen alle Objekte permutiert werden, d.h. \(k=n\):

\[ ^nP = ^nP_n = n! \]

Videos

    • Kombinationen – Pralinenschachtel (5053-6)

      Dauer: 11 min 24 s

    • k-Permutationen (Variationen) – Strassenschilder (5052-4)

    • k-Permutationen (Variationen) – Passwort (5052-5)

    • k-Permutationen (Variationen) – Spielabend unter Freunden (5052-6)

    • k-Permutationen – Variationen (Teil 1) (Tutorial)

      Dauer: 8 min 55 s

    • k-Permutationen – Variationen (Teil 2) (Tutorial)

      Dauer: 16 min 16 s

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

    Wie bei den Permutationen behalten wir bei den \(k\)-Permutationen die Reihenfolge, d.h. wir unterscheiden beispielsweise zwischen \((A,B)\) und \((B,A)\).

    k-Permutation mit Zurücklegen

    Wir schauen uns für eine k-Permutation zuerst ein einfaches Beispiel an. Daraus werden wir die allgemeine Formel ableiten können.

    Beispiel: Knacken eines Zahlenschlosses

    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 erlaubt sein – sie darf mehrfach 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:

    \[ \overline{^{10}P_4} = 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10’000 \]

    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, d.h. den Umstand, dass sich Ziffern wiederholen dürfen.

    Wir können das jetzt verallgemeinern:

    Für eine k-Permutation von \(k\) Objekten aus einer Grundmenge von \(n\) Objekten, mit Zurücklegen der Objekte nach jedem Zug, ist die Anzahl Möglichkeiten: 

    \[ \overline{^nP_k} = n \cdot n \cdot n \cdot \;…\; \cdot n \;\;=\;\; n^k \]

    “Permutationen sind eine Untermenge der k-Permutationen”

    k-Permutation ohne Zurücklegen

    Wir werden auch die allgemeine Formel anhand eines Beispiels kennenlernen:

    Beispiel: Podestbesetzungen bei einem Rennen

    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 der Ziellinie ist es, drei Sportler aus dem Pool der 20 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 20 Teilnehmer zur Wahl. Für den zweiten sind es noch 19 und für den Dritten noch 18. Wir verknüpfen die Möglichkeiten mit dem Produkt gemäss Fundamentalprinzip der Kombinatorik und erhalten so für die möglichen Podest-Besetzungen:

    \[ ^nP_3 = 20 \cdot 19 \cdot 18 = \underline{6’840} \]

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

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

    \[ ^nP_k = n \cdot (n-1) \cdot (n-2) \cdot \;…\; \cdot (n-k+1) \]

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

    \[ \require{cancel} ^nP_k = \frac{n \cdot (n-1) \cdot (n-2) \cdot \;…\; (n-k+1) \cdot \cancel{(n-k) \cdot (n-k-1) \cdot \;…\; \cdot 2 \cdot 1}}{\cancel{(n-k) \cdot (n-k-1) \cdot \;…\; \cdot 2 \cdot 1}} \]

    \[ ^nP_k = \frac{n \cdot (n-1) \cdot (n-2) \cdot \;…\; \cdot 2 \cdot 1}{(n-k) \cdot (n-k-1) \cdot \;…\; \cdot 2 \cdot 1} \]

    \[ ^nP_k = \frac{n!}{(n-k)!} \]

    Wir überprüfen kurz, ob wir für das obige Beispiel (\(n=20, k=3\)) das gleiche Resultat erhalten:

    \[ ^{20}P_3 = \frac{20!}{(20-3)!} = \frac{20!}{17!} = 6’840 \]

    Zähler und Nenner werden unglaublich gross, aber das Resultat stimmt überein. Wir halten deshalb fest:

    Eine k-Permutation von \(k\) Objekten aus einer Grundmenge von \(n\) Objekten, ohne Zurücklegen der Objekte, hat die folgende Anzahl Möglichkeiten:

    \[ ^nP_k = \frac{n!}{(n-k)!} \]

    Permutationen sind eine Untermenge von k-Permutationen

    Beachte, dass wenn wir gleich viele Objekte ziehen, wie es Objekte in der Grundmenge hat, d.h. \(k=n\), so wird aus der \(k\)-Permutation eine normale Permutation von \(n\) Objekten. Die Anzahl \(n\)-Permutationen ist dann:

    \[ ^nP_n = \frac{n!}{(n-k)!} = \frac{n!}{(n-n)!} = \frac{n!}{0!} \]

    Jetzt benutzen wir den Umstand dass \(0!=1\) und erhalten so:

    \[ = \frac{n!}{1} = n! = \; ^nP \]

    Wir sehen, dass wir das gleiche Resultat erhalten, wie für die “normale” Permutation von \(n\) Objekten.

    Was ist die Fakultät von null?

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

    \[ 0! = 1 \]

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

    \[ \require{cancel} \frac{5!}{5} = \frac{\cancel{5} \cdot 4 \cdot 3 \cdot 2 \cdot 1}{\cancel{5}} = 4! \]

    \[ \frac{4!}{4} = 3! \]

    \[ \frac{3!}{3} = 2! \]

    Somit wird die Zahl links um eins reduziert:

    \[ \frac{n!}{n} = (n-1)! \]

    Wenn wir jetzt links 1 setzen, erhalten wir:

    \[ \frac{1!}{1} = \frac{1}{1} = (1-1)! = 0! \]

    Aus diesem Grund merken wir uns: \(0! = 1\)

    Aufgabensammlung

    • Binomialkoeffizient und Kombinationen (5053) – Aufg. 6

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

      zur Aufgabe
    • Permutationen (5052) – Aufg. 4

      4 Teilaufgaben (pdf/Video-Lösung):
      Strassenschilder (Textaufgabe)

      zur Aufgabe
    • Permutationen (5052) – Aufg. 5

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

      zur Aufgabe
    • Permutationen (5052) – Aufg. 6

      3 Teilaufgaben (pdf/Video-Lösung):
      Spielabend unter Freunden (Textaufgabe)

      zur Aufgabe

    Lernziele

    • Du weisst, was eine k-Permutation (Variation) ist und welche Gemeinsamkeiten und Unterschiede sie mit einer ”normalen” Permutation hat.
    • Du kannst zwischen den Fällen mit und ohne Zurücklegen unterscheiden und dementsprechend die Anzahl möglicher k-Permutation berechnen.

    Weitere Links

    Variation (Wikipedia)

    Feedback

    Post Feedback Form

    Autor dieses Artikels:

    David John Brunner

    Lehrer für Physik und Mathematik | Mehr erfahren

    publiziert:

    überarbeitet:

    publiziert:

    überarbeitet:

    Frage oder Kommentar?

    Frage/Kommentar?

    Schreib deine Frage / Kommentar hier unten rein. Ich werde sie beantworten.

    Schreibe einen Kommentar