k-Permutationen (Variationen)

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.

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 \]

k-Permutation ohne Zurücklegen

Wir werden auch die allgemeine Formel anhand eines Beispiels kennenlernen:

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\)