Variation (Kombinatorik)

Eine Variation (von lateinisch variatio „Veränderung“) o​der geordnete Stichprobe i​st in d​er Kombinatorik e​ine Auswahl v​on Objekten a​us einer Menge i​n einer bestimmten Reihenfolge. Können Objekte d​abei mehrfach ausgewählt werden, s​o spricht m​an von e​iner Variation m​it Wiederholung, d​arf jedes Objekt n​ur einmal auftreten, v​on einer Variation o​hne Wiederholung. Die Ermittlung d​er Anzahl möglicher Variationen i​st eine Standardaufgabe d​er abzählenden Kombinatorik.

Begriffsabgrenzung

Eine Variation oder geordnete Stichprobe ist eine Auswahl von ${\displaystyle k}$ Objekten aus einer Menge von ${\displaystyle n}$ Objekten, wobei die Reihenfolge der Auswahl eine Rolle spielt. Werden alle verfügbaren Objekte ausgewählt, gilt also ${\displaystyle 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.[1]

Bei e​iner Variation m​it Wiederholung können Objekte mehrfach ausgewählt werden, während b​ei einer Variation o​hne Wiederholung j​edes Objekt n​ur einmal auftreten darf. In e​inem Urnenmodell entspricht e​ine Variation m​it Wiederholung e​iner Ziehung d​er Kugeln m​it Zurücklegen u​nd eine Variation o​hne Wiederholung e​iner Ziehung o​hne Zurücklegen.[1]

Davon abweichend werden i​n der Literatur manchmal a​uch Variationen u​nd Kombinationen zusammengefasst u​nd eine Variation w​ird dann „Kombination m​it Berücksichtigung d​er Reihenfolge“ genannt.[2] Insbesondere i​m englischen Sprachgebrauch werden a​uch Variationen u​nd Permutationen zusammengefasst u​nd Variationen d​ann „k-Permutationen“ (k-permutations) genannt.[3]

Variation ohne Wiederholung

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

Anzahl

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

${\displaystyle 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 ${\displaystyle n^{\underline {k}}}$ und ${\displaystyle (n)_{k}}$, die fallende Faktorielle genannt werden. Mit ${\displaystyle n!}$ wird die Fakultät von ${\displaystyle n}$ bezeichnet.

Mengendarstellung

Die Menge

${\displaystyle \{(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 ${\displaystyle n}$ Objekten zur Klasse ${\displaystyle k}$“ 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ Objekten ${\displaystyle k}$ Objekte unter Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können. Nachdem jedes der ${\displaystyle n}$ Objekte auf jedem der ${\displaystyle k}$ Plätze der Auswahl erscheinen kann, gibt es demzufolge

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

mögliche Anordnungen.

Mengendarstellung

Die Menge

${\displaystyle \{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 ${\displaystyle n}$ Objekten zur Klasse ${\displaystyle k}$“. Sie ist das ${\displaystyle k}$-fache kartesische Produkt der Menge ${\displaystyle \{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 ${\displaystyle 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 ${\displaystyle 10^{4}=10000}$ verschiedene Variationen (0000–9999).
• In der Digitaltechnik verwendete Binärzahlen bestehen nur aus den beiden Ziffern ${\displaystyle 0}$ und ${\displaystyle 1}$. Mit einer Anordnung von ${\displaystyle k}$ solchen Ziffern können dementsprechend ${\displaystyle 2^{k}}$ verschiedene Variationen entstehen. Eine vierstellige Binärzahl kodiert beispielsweise ${\displaystyle 2^{4}=16}$ verschiedene Zustände.

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1.
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1.
• Joachim Hartung, Bärbel Elpelt, Karl-Heinz Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. Oldenbourg, 2005, ISBN 3-486-57890-1.

Einzelnachweise

1. Bronstein, Semendjajew: Taschenbuch der Mathematik. Harri Deutsch, 2008, ISBN 3-8171-2007-9, S. 810–811.
2. Hartung, Elpelt, Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. S. 96.
3. Aigner: Diskrete Mathematik. S. 7.