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 Bearbeiten
Eine Variation oder Stichprobe mit Berücksichtigung der Reihenfolge der gezogenen Elemente ist eine Auswahl von Objekten aus einer Menge von Objekten, wobei die Reihenfolge der Auswahl berücksichtigt wird. Werden alle verfügbaren Objekte ausgewählt, gilt also , 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.
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. Eine Variation ohne Wiederholung ist eine Stichprobe ohne Zurücklegen des Umfangs aus einer Grundgesamtheit von Elementen, wobei die Reihenfolge der gezogenen Elemente berücksichtigt wird, oder kurz eine 'geordnete Auswahl ohne Zurücklegen'. Eine Variation mit Wiederholung ist eine Stichprobe mit Zurücklegen des Umfangs aus einer Grundgesamtheit von Elementen, wobei die Reihenfolge der gezogenen Elemente berücksichtigt wird, oder kurz eine 'geordnete Auswahl mit Zurücklegen'.
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.
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 werden dann partial permutations oder k-permutations genannt.
Variation ohne Wiederholung Bearbeiten
Anzahl Bearbeiten
Bei einer Variation ohne Wiederholung sollen von Objekten (mit ) 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 Objekte usw. bis zum -ten Platz, für den es noch mögliche Objekte gibt. Insgesamt gibt es also
mögliche Anordnungen. Für diese Zahl existieren auch die Notationen und , die fallende Faktorielle genannt werden. Mit wird die Fakultät von bezeichnet.
Mengendarstellung Bearbeiten
Die Menge
ist die Menge aller Variationen ohne Wiederholung von Objekten zur Klasse und hat die oben angegebene Anzahl von Elementen.
Beispiele Bearbeiten
Urne mit Kugeln Bearbeiten
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 verschiedene Auswahlmöglichkeiten, wenn die Reihenfolge der gezogenen Kugeln betrachtet wird.
Sollen alle 5 Kugeln ausgewählt werden, ergeben sich dementsprechend insgesamt Möglichkeiten, also die Anzahl der Permutationen aller 5 Kugeln.
Personen und Sitzplätze Bearbeiten
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 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 mögliche Sitzordnungen.
Teams und Positionen Bearbeiten
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 . 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 Bearbeiten
Jede Variation ohne Wiederholung kann formal als injektive Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden. Die Definitionsmenge hat Elemente und die Zielmenge hat Elemente. Dann stellt jede injektive Funktion eine Variation ohne Wiederholung dar.
Für gibt es mögliche Funktionswerte, nämlich . Für gibt es dann noch mögliche Funktionswerte, nämlich mit Ausnahme von . Für gibt es dann noch mögliche Funktionswerte, nämlich mit Ausnahme von . Diese Argumentation lässt sich fortsetzen. Für gibt es schließlich noch mögliche Funktionswerte, nämlich mit Ausnahme von . Daraus ergeben sich insgesamt mögliche injektive Funktionen , was der Anzahl der Variationen ohne Wiederholung entspricht.
Variation mit Wiederholung Bearbeiten
Anzahl Bearbeiten
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
mögliche Anordnungen.
Mengendarstellung Bearbeiten
Die Menge
ist die Menge aller Variationen mit Wiederholung von Objekten zur Klasse . Sie ist das -fache kartesische Produkt der Menge mit sich selbst und hat die oben angegebene Anzahl von Elementen.
Beispiele Bearbeiten
Würfel Bearbeiten
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 mögliche Ergebnisse.
Urne mit Kugeln Bearbeiten
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 verschiedene Auswahlmöglichkeiten, wenn die Reihenfolge der gezogenen Kugeln betrachtet wird.
Identifikationsnummern und Zahlen in einem Stellenwertsystem Bearbeiten
Bei einer 4-stelligen PIN oder einem Zahlenschloss mit 4 Ringen und je 10 Ziffern gibt es insgesamt 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 und . Mit einer Anordnung von Binärziffern (Bits) können dementsprechend verschiedene Variationen entstehen. Eine 4-stellige Binärzahl kodiert beispielsweise verschiedene Zustände.
Allgemein ist die Anzahl der natürlichen Zahlen mit Ziffern (-stelligen natürlichen Zahlen) im Stellenwertsystem der Basis gleich , wenn die Zahlen, die mit der Ziffer 0 beginnen, mitgezählt werden. Dann ist nach der oben genannten Definition also .
Rastergrafiken Bearbeiten
Eine digitale Rastergrafik hat die Bildauflösung 1280 × 720 Pixel, also eine Anzahl von 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 mögliche Zustände und jedes Pixel mögliche Werte. Gesucht ist die Anzahl aller möglichen Rastergrafiken. In diesem Fall ist und . Daraus ergibt sich die unvorstellbare Anzahl von möglichen digitalen Rastergrafiken, wenn die Farbwerte verlustfrei komprimiert und gespeichert werden.
Darstellung als Funktion Bearbeiten
Jede Variation mit (möglicher) Wiederholung kann formal als Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden. Die Definitionsmenge hat Elemente und die Zielmenge hat Elemente. Dann stellt jede Funktion eine Variation mit (möglicher) Wiederholung dar.
Für gibt es mögliche Funktionswerte, nämlich . Für gibt es ebenfalls diese möglichen Funktionswerte. Diese Argumentation lässt sich fortsetzen. Auch für gibt es schließlich diese möglichen Funktionswerte. Daraus ergeben sich insgesamt mögliche Funktionen , was der Anzahl der Variationen mit Wiederholung entspricht.
Literatur Bearbeiten
- 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 Bearbeiten
- ↑ Bronstein, Semendjajew: Taschenbuch der Mathematik. Harri Deutsch, 2008, ISBN 3-8171-2007-9, S. 810–811.
- ↑ Horst Rinne: Taschenbuch der Statistik. 4. Auflage. Harri Deutsch, Frankfurt am Main 2008, ISBN 978-3-8171-1827-4, S. 169.
- 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.
- 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.
- Hartung, Elpelt, Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. S. 96.
- Aigner: Diskrete Mathematik. S. 7.
- ↑ Klaus Sutner, Carnegie Mellon University: CDM Combinatorics
- Maria Axenovich, Torsten Ueckerdt, Jonathan Rollin, Stefan Walzer, Karlsruher Institut für Technologie: Lecture Notes - Combinatorics, Seite 27 und 28