Variation (Kombinatorik)

Eine Variation (von lateinisch variatio ‚Veränderung‘) ist in der Kombinatorik eine Auswahl von Objekten aus einer Menge 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. Bei einer Variation wird die Reihenfolge der ausgewählten Objekte berücksichtigt, was bei einer Kombination nicht der Fall ist. Die Ermittlung der Anzahl möglicher Variationen ist eine Standardaufgabe der abzählenden Kombinatorik.

Begriffsabgrenzung

Eine Variation oder Stichprobe mit Berücksichtigung der Reihenfolge der gezogenen Elemente ist eine Auswahl von ${\displaystyle k}$ Objekten aus einer Menge von ${\displaystyle n}$ Objekten, wobei die Reihenfolge der Auswahl berücksichtigt wird. Werden alle verfügbaren Objekte ausgewählt, gilt also ${\displaystyle k=n}$, so spricht man statt von einer Variation von einer Permutation. Wird bei der Auswahl der Objekte die Reihenfolge nicht berücksichtigt, dann entsteht eine Kombination.^[1]

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, jeweils mit Berücksichtigung der Reihenfolge der gezogenen Elemente.^[1] Eine Variation ohne Wiederholung ist eine Stichprobe ohne Zurücklegen des Umfangs ${\displaystyle k}$ aus einer Grundgesamtheit von ${\displaystyle n}$ Elementen, wobei die Reihenfolge der gezogenen Elemente berücksichtigt wird, oder kurz eine 'geordnete Auswahl ohne Zurücklegen'.^[2] Eine Variation mit Wiederholung ist eine Stichprobe mit Zurücklegen des Umfangs ${\displaystyle k}$ aus einer Grundgesamtheit von ${\displaystyle n}$ Elementen, wobei die Reihenfolge der gezogenen Elemente berücksichtigt wird, oder kurz eine 'geordnete Auswahl mit Zurücklegen'.^[2]

Das Konzept einer Stichprobe mit Berücksichtigung der Reihenfolge der gezogenen Elemente (auch geordnete Auswahl genannt) darf nicht mit dem Konzept der 'geordneten Stichprobe' verwechselt werden. Eine geordnete Stichprobe entsteht, wenn die Werte einer Stichprobe einen Größenvergleich erlauben und der Größe nach angeordnet werden.^[3][4]

Davon abweichend werden in der Literatur manchmal auch Variationen und Kombinationen zusammengefasst und eine Variation wird dann Kombination mit Berücksichtigung der Reihenfolge genannt.^[5] Insbesondere im englischen Sprachgebrauch werden auch Variationen und Permutationen zusammengefasst und Variationen werden dann partial permutations oder k-permutations genannt.^[6]

Variation ohne Wiederholung

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

Urne mit Kugeln

Aus einer Urne mit 5 nummerierten Kugeln wird 3-mal eine Kugel ohne Zurücklegen gezogen. Für die Auswahl der ersten Kugel gibt es dann 5 Möglichkeiten, für die zweite Kugel 4 Möglichkeiten und für die dritte Kugel 3 Möglichkeiten. Insgesamt gibt es daher ${\displaystyle 5\cdot 4\cdot 3=60}$ verschiedene Auswahlmöglichkeiten, wenn die Reihenfolge der gezogenen Kugeln betrachtet wird.

Sollen alle 5 Kugeln ausgewählt werden, ergeben sich dementsprechend insgesamt ${\displaystyle 5\cdot 4\cdot 3\cdot 2\cdot 1=5!=120}$ Möglichkeiten, also die Anzahl der Permutationen aller 5 Kugeln.

Personen und Sitzplätze

9 Personen wollen sich in ein Zugabteil mit 4 Sitzplätzen setzen. Gesucht ist die Anzahl der möglichen Sitzordnungen, wenn alle Plätze einmal besetzt und die Personen ohne Sitzplatz nicht betrachtet werden. Der erste Sitzplatz kann von 9, der zweite von 8, der dritte von 7 und der vierte Sitzplatz kann von 6 möglichen Personen besetzt werden. Daraus ergeben sich ${\displaystyle 9\cdot 8\cdot 7\cdot 6=3024}$ mögliche Sitzordnungen.

Eine andere Situation ist folgende: 4 Personen wollen sich in ein Flugzeugabteil mit 9 Sitzplätzen setzen. Gesucht ist die Anzahl der möglichen Sitzordnungen, wenn alle Personen einen Platz besetzen und jeder Platz höchstens einmal besetzt wird. Die erste Person besetzt einen von 9, die zweite einen von 8, die dritte einen von 7 und die vierte Person besetzt einen von 6 möglichen Sitzplätzen. Daraus ergeben sich ${\displaystyle 9\cdot 8\cdot 7\cdot 6=3024}$ mögliche Sitzordnungen.

Teams und Positionen

In einem Team werden 7 verschiedene Positionen jeweils mit einer Person besetzt. Es stehen insgesamt 10 Personen zur Auswahl. Für die erste Position gibt es 10 mögliche Personen. Für die siebte Position gibt es schließlich noch 4 Kandidaten. Die Anzahl der Zuordnungsmöglichkeiten für die 7 Positionen ist daher gleich ${\displaystyle 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4=604800}$. Wenn in einem Teamsport jeder Sportler eine bestimmte Position übernimmt und jeder Sportler für jede Position zur Verfügung steht, kann jede Aufstellung als Variation ohne Wiederholung angesehen werden. Bei einigen Sportarten werden die Positionen mit Rückennummern gekennzeichnet, die eindeutig nummeriert sind. In solchen Fällen ist die Anzahl der möglichen Aufstellungen allerdings praktisch wenig relevant, denn nicht jeder Sportler steht für jede Position zur Verfügung und verschiedene Rückennummern stehen nicht unbedingt für verschiedene Positionen.

Darstellung als injektive Funktion

Jede Variation ohne Wiederholung kann formal als injektive Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.^[7] Die Definitionsmenge ${\displaystyle X:=\{x_{1},x_{2},\ldots ,x_{k}\}}$ hat ${\displaystyle k}$ Elemente und die Zielmenge ${\displaystyle Y:=\{y_{1},y_{2},\ldots ,y_{n}\}}$ hat ${\displaystyle n}$ Elemente. Dann stellt jede injektive Funktion ${\displaystyle f\colon \,X\to Y}$ eine Variation ohne Wiederholung dar.

Für ${\displaystyle f(x_{1})}$ gibt es ${\displaystyle n}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$. Für ${\displaystyle f(x_{2})}$ gibt es dann noch ${\displaystyle n-1}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1})}$. Für ${\displaystyle f(x_{3})}$ gibt es dann noch ${\displaystyle n-2}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1}),f(x_{2})}$. Diese Argumentation lässt sich fortsetzen. Für ${\displaystyle f(x_{k})}$ gibt es schließlich noch ${\displaystyle n-k+1}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1}),f(x_{2}),\ldots ,f(x_{k-1})}$. Daraus ergeben sich insgesamt ${\displaystyle n\cdot (n-1)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}}$ mögliche injektive Funktionen ${\displaystyle f\colon \,X\to Y}$, was der Anzahl der Variationen ohne Wiederholung entspricht.^[8]

Variation mit Wiederholung

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

Würfel

Ein Spielwürfel mit 1 bis 6 Augen wird 4-mal geworfen und jedes Mal die gewürfelte Augenzahl notiert. Bei jedem der 4 Würfe gibt es 6 mögliche Ergebnisse. Für die 4 Würfe gibt es daher insgesamt ${\displaystyle 6\cdot 6\cdot 6\cdot 6=6^{4}=1296}$ mögliche Ergebnisse.

Urne mit Kugeln

Aus einer Urne mit 5 nummerierten Kugeln wird 3-mal eine Kugel mit Zurücklegen gezogen. Für die Auswahl jeder Kugel gibt es dann 5 Möglichkeiten. Insgesamt gibt es also ${\displaystyle 5\cdot 5\cdot 5=5^{3}=125}$ verschiedene Auswahlmöglichkeiten, wenn die Reihenfolge der gezogenen Kugeln betrachtet wird.

Identifikationsnummern und Zahlen in einem Stellenwertsystem

Bei einer 4-stelligen PIN oder einem Zahlenschloss mit 4 Ringen und je 10 Ziffern gibt es insgesamt ${\displaystyle 10^{4}=10000}$ verschiedene Variationen. Das sind die Zahlen 0000 bis 9999, also alle 4-stelligen natürlichen Zahlen im Dezimalsystem, wenn die Zahlen, die mit der Ziffer 0 beginnen, mitgezählt werden.

In der Digitaltechnik verwendete Binärzahlen bestehen nur aus den 2 Ziffern ${\displaystyle 0}$ und ${\displaystyle 1}$. Mit einer Anordnung von ${\displaystyle k}$ Binärziffern (Bits) können dementsprechend ${\displaystyle 2^{k}}$ verschiedene Variationen entstehen. Eine 4-stellige Binärzahl kodiert beispielsweise ${\displaystyle 2^{4}=16}$ verschiedene Zustände.

Allgemein ist die Anzahl der natürlichen Zahlen mit ${\displaystyle n}$ Ziffern (${\displaystyle n}$-stelligen natürlichen Zahlen) im Stellenwertsystem der Basis ${\displaystyle b}$ gleich ${\displaystyle b^{n}}$, wenn die Zahlen, die mit der Ziffer 0 beginnen, mitgezählt werden. Dann ist nach der oben genannten Definition also ${\displaystyle k=b}$.

Rastergrafiken

Eine digitale Rastergrafik hat die Bildauflösung 1280 × 720 Pixel, also eine Anzahl von ${\displaystyle 1280\cdot 720=921600}$ Pixeln. Jedes Pixel wird im RGB-Farbraum gespeichert und hat 3 Farbkanäle. Jeder der 3 Farbkanäle hat 8 Bit. Jeder Farbkanal hat demnach ${\displaystyle 2^{8}=256}$ mögliche Zustände und jedes Pixel ${\displaystyle 256^{3}=16777216}$ mögliche Werte. Gesucht ist die Anzahl aller möglichen Rastergrafiken. In diesem Fall ist ${\displaystyle n=16777216}$ und ${\displaystyle k=921600}$. Daraus ergibt sich die unvorstellbare Anzahl von ${\displaystyle 16777216^{921600}}$ möglichen digitalen Rastergrafiken, wenn die Farbwerte verlustfrei komprimiert und gespeichert werden.

Darstellung als Funktion

Jede Variation mit (möglicher) Wiederholung kann formal als Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.^[7] Die Definitionsmenge ${\displaystyle X:=\{x_{1},x_{2},\ldots ,x_{k}\}}$ hat ${\displaystyle k}$ Elemente und die Zielmenge ${\displaystyle Y:=\{y_{1},y_{2},\ldots ,y_{n}\}}$ hat ${\displaystyle n}$ Elemente. Dann stellt jede Funktion ${\displaystyle f\colon \,X\to Y}$ eine Variation mit (möglicher) Wiederholung dar.

Für ${\displaystyle f(x_{1})}$ gibt es ${\displaystyle n}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$. Für ${\displaystyle f(x_{2})}$ gibt es ebenfalls diese ${\displaystyle n}$ möglichen Funktionswerte. Diese Argumentation lässt sich fortsetzen. Auch für ${\displaystyle f(x_{k})}$ gibt es schließlich diese ${\displaystyle n}$ möglichen Funktionswerte. Daraus ergeben sich insgesamt ${\displaystyle \underbrace {n\cdot \dotsc \cdot n} _{k{\text{-mal}}}=n^{k}}$ mögliche Funktionen ${\displaystyle f\colon \,X\to Y}$, was der Anzahl der Variationen mit Wiederholung entspricht.

Literatur

• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1. 
• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-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. ↑ ^{a b} Bronstein, Semendjajew: Taschenbuch der Mathematik. Harri Deutsch, 2008, ISBN 3-8171-2007-9, S. 810–811. 
2. ↑ ^{a b} Horst Rinne: Taschenbuch der Statistik. 4. Auflage. Harri Deutsch, Frankfurt am Main 2008, ISBN 978-3-8171-1827-4, S. 169. 
3. ↑ P. H. Müller (Hrsg.): Lexikon der Stochastik – Wahrscheinlichkeitsrechnung und mathematische Statistik. 5. Auflage. Akademie-Verlag, Berlin 1991, ISBN 978-3-05-500608-1, geordnete Stichprobe, S. 141. 
4. ↑ Guido Walz (Hrsg.): Lexikon der Mathematik. 2. Auflage. Band 2. Eig bis Inn. Springer Spektrum, Berlin 2017, ISBN 978-3-662-53503-5, geordnete Stichprobe, S. 277, doi:10.1007/978-3-662-53504-2. 
5. ↑ Hartung, Elpelt, Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. S. 96. 
6. ↑ Aigner: Diskrete Mathematik. S. 7. 
7. ↑ ^{a b} Klaus Sutner, Carnegie Mellon University: CDM Combinatorics
8. ↑ Maria Axenovich, Torsten Ueckerdt, Jonathan Rollin, Stefan Walzer, Karlsruher Institut für Technologie: Lecture Notes - Combinatorics, Seite 27 und 28