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

In zwei Videos wird die Theorie erklärt und mit Beispielen illustriert.

Um das Video anzusehen, musst du einloggen
Noch kein Login? Hier registrieren

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:

\[ ^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:

\[ \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$

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.

Mini-Test

(zu diesem Thema gibt es noch keinen Mini-Test)

Weitere Links


Physik- und Mathe-Hacks lernen…

…im Hacker-Club!

Aufgabensammlung

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 6

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

  • Permutationen (5052) – Aufg. 4

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

  • Permutationen (5052) – Aufg. 5

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

  • Permutationen (5052) – Aufg. 6

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