Variation (Kombinatorik)

Eine Variation (von lateinisch variatio „Veränderung“) oder geordnete Stichprobe ist in der Kombinatorik eine Auswahl von Objekten in einer bestimmten Reihenfolge. Können Objekte dabei mehrfach ausgewählt werden, so spricht man von einer Variation mit Wiederholung, darf jedes Objekt nur einmal auftreten von einer Variation ohne Wiederholung. Die Ermittlung der Anzahl möglicher Variationen ist eine Standardaufgabe der abzählenden Kombinatorik.

Begriffsabgrenzung

Eine Variation oder geordnete Stichprobe ist eine Auswahl von Objekten aus einer Menge von Objekten, wobei die Reihenfolge der Auswahl eine Rolle spielt. Werden alle verfügbaren Objekte ausgewählt, gilt also k=n , so spricht man statt von einer Variation von einer Permutation, spielt bei der Auswahl der Objekte die Reihenfolge keine Rolle von einer Kombination.

Bei einer Variation mit Wiederholung können Objekte mehrfach ausgewählt werden, während bei einer Variation ohne Wiederholung jedes Objekt nur einmal auftreten darf. In einem Urnenmodell entspricht eine Variation mit Wiederholung einer Ziehung der Kugeln mit Zurücklegen und eine Variation ohne Wiederholung einer Ziehung ohne Zurücklegen.

Davon abweichend werden in der Literatur manchmal auch Variationen und Kombinationen zusammengefasst und eine Variation wird dann „Kombination mit Berücksichtigung der Reihenfolge“ genannt. Insbesondere im englischen Sprachgebrauch werden auch Variationen und Permutationen zusammengefasst und Variationen dann „k-Permutationen“ (k-permutations) genannt.

Variation ohne Wiederholung

Alle 60 Variationen ohne Wiederholung von drei aus fünf Zahlen

Anzahl

Bei einer Variation ohne Wiederholung sollen von Objekten (mit $k\leq n$ ) auf verfügbare Plätze platziert werden, wobei jedes Objekt nur höchstens einen Platz einnehmen darf. Es gibt für den ersten Platz mögliche Objekte, für den zweiten Platz n-1 Objekte usw. bis zum -ten Platz, für den es noch n-k+1 mögliche Objekte gibt. Insgesamt gibt es also

$n\cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$

mögliche Anordnungen. Für diese Zahl existieren auch die Notationen $n^{\underline{k}}$ und (n)_k , die fallende Faktorielle genannt werden. Mit wird die Fakultät von bezeichnet.

Mengendarstellung

Die Menge

$\{ (x_1, x_2, \dotsc, x_{k}) \mid x_i \in \{1, 2, \dotsc, n\}, x_i \neq x_j ~\text{für}~i \neq j \}$

ist die „Menge aller Variationen ohne Wiederholung von Objekten zur Klasse “ und hat die oben angegebene Anzahl von Elementen.

Beispiele

Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal ohne Zurücklegen gezogen wird, sind $5 \cdot 4 \cdot 3 = 60$ verschiedene Auswahlen möglich: bei der ersten Ziehung noch fünf Möglichkeiten, dann nur noch vier und für die dritte Ziehung schließlich nur noch drei Möglichkeiten.
Sollen alle fünf Kugeln ausgewählt werden, ergibt sich dementsprechend eine Zahl von insgesamt $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120$ Möglichkeiten, also die Zahl der Permutationen aller fünf Kugeln.

Variation mit Wiederholung

Alle 125 Variationen mit Wiederholung von drei aus fünf Zahlen

Anzahl

Bei einer Variation mit Wiederholung werden aus Objekten Objekte unter Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können. Nachdem jedes der Objekte auf jedem der Plätze der Auswahl erscheinen kann, gibt es demzufolge

$\underbrace{n \cdot \dotsc \cdot n}_{k\text{-mal}} = n^k$

mögliche Anordnungen.

Mengendarstellung

Die Menge

$\{1, 2, \dotsc, n\}^k = \bigl\{(x_1, x_2, \dotsc, x_{k}) \mid x_{i} \in \{1, 2, \dotsc, n\} \bigl\}$

ist die „Menge aller Variationen mit Wiederholung von Objekten zur Klasse “. Sie ist das -fache kartesische Produkt der Menge $\{1, 2, \dotsc, n\}$ mit sich selbst und hat die oben angegebene Anzahl von Elementen.

Beispiele

Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal mit Zurücklegen gezogen wird, dann sind $5 \cdot 5 \cdot 5 = 5^3 = 125$ verschiedene Auswahlen möglich.
Bei einer vierstelligen PIN oder einem Zahlenschloss mit vier Ringen und je zehn Ziffern gibt es insgesamt verschiedene Variationen (0000–9999).
In der Digitaltechnik verwendete Binärzahlen bestehen nur aus den beiden Ziffern $0$ und . Mit einer Anordnung von solchen Ziffern können dementsprechend $2^{k}$ verschiedene Variationen entstehen. Eine vierstellige Binärzahl kodiert beispielsweise verschiedene Zustände.

Basierend auf einem Artikel in:

Wikipedia.de