Variation (Kombinatorik)

Grundbegriffe

Variation

Jede Zusammenstellung von $k$ Elementen aus $n$ Elementen, die sich unter Berücksichtigung ihrer Anordnung ergibt, wird als Variation von $n$ Elementen zur $k$-ten Ordnung bezeichnet.

Variation mit Wiederholung

Bei der Variation mit Wiederholung kann jedes Element wiederholt in der Zusammenstellung vorkommen.

Die Anzahl der möglichen Variationen von $n$ Elementen zur $k$-ten Ordnung mit Wiederholung, symbolisiert mit $V^{W}(n;k)$, ist:

$V^{W}(n;k)=n^{k}$

Variation ohne Wiederholung

Bei diesen Variationen kann jedes Element nur einmal in der Zusammenstellung vorkommen.

Die Anzahl der möglichen Variationen von $n$ Elementen zur $k$-ten Ordnung ohne Wiederholung, symbolisiert mit $V(n;k)$ ist:

$V(n;k)=n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot (n-k+2)\cdot (n-k+1)={\frac {n\,!}{(n-k)\,!}}$

Beispiele

Variation mit Wiederholung

Beispiele mit den Elementen $a$, $b$ und $c$ ($n=3$):

• Für $k=1$ ist $V^{W}(3;1)=3^{1}=3$.

Die drei möglichen Variationen sind:

$a$ $b$ $c$

• Für $k=2$ ist $V^{W}(3;2)=3^{2}=9$

Die neun möglichen Variationen sind:

$aa$ $ab$ $ac$

$ba$ $bb$ $bc$

$ca$ $cb$ $cc$

• Für $k=3$ ist $V^{W}(3;3)=3^{3}=27$.

Die 27 möglichen Variationen sind:

$aaa$ $aab$ $aac$

$aba$ $abb$ $abc$

$aca$ $acb$ $acc$

$baa$ $bab$ $bac$

$bba$ $bbb$ $bbc$

$bca$ $bcb$ $bcc$

$caa$ $cab$ $cac$

$cba$ $cbb$ $cbc$

$cca$ $ccb$ $ccc$

Variation ohne Wiederholung

Beispiele mit den Elementen $a$, $b$ und $c$ ($n=3$):

• Für $k=1$ ist $V(3;1)=3!/2!=3$.

Die drei möglichen Variationen sind:

$a$ $b$ $c$

• Für $k=2$ ist $V(3;2)=3!/1!=6$. Die sechs möglichen Variationen sind:

$abc$

$acb$

$bac$

$bca$

$cab$

$cba$

Smartephone PIN

Bei den meisten der heutzutage genutzten Smartphones lässt sich das Display mit der Option "PIN" sperren.

Es stellt sich nun die Frage, wie viele mögliche Zahlenanordnungen gibt es?

Meist handelt es sich um einen Code aus 4 Zahlen, welche die Werte zwischen 0 und 9 annehmen können.

Es liegt in diesem Fall also eine Zusammenstellung von 4 Zahlen ($k$ Elementen) aus 10 Zahlen ($n$ Elemente) vor.

Desweiteren ist von Bedeutung, wie die Zahlen angeordnet sind (Reihenfolge), da beispielsweise die Zahlenfolge 4621 eine andere Wirkung haben kann als die Zahlenfolgen 1264 oder 4126.

Diese beiden Informationen ($k$ Elemente aus $n$ Elementen, Berücksichtigung der Anordnung) führen zur Variation als Lösungsansatz. (Der umgangssprachlich häufig angewandte Begriff Zahlenkombination ist an dieser Stelle sachlich falsch - vielmehr handelt es sich um eine Zahlenvariation!)

Die Variation eröffnet wiederum zwei Möglichkeiten: Variation ohne Wiederholung und Variation mit Wiederholung.

Da jede der Zahlen der PIN Werte zwischen 0 und 9 annehmen kann (4444 also zum Beispiel möglich ist), handelt es sich um eine Variation mit Wiederholung.

$k=4$

$n=10$ (0 bis 9)

$\,V^{W}=(n,k)=n^{k}$

$V^{W}=(10,4)=10^{4}=10\cdot 10\cdot 10\cdot 10=10000$

Ein Zahlenschloss mit 4 zu wählenden Zahlen (0 bis 9) ermöglicht 10000 Variationen.

Bei 1 Sekunde pro Öffnungsversuch werden also im Höchstfall $(1\cdot 10000)=2,77$ Stunden benötigt, um alle PINs einmal durchzuprobieren.