Variation (Kombinatorik)

Auswahl von Objekten in einer bestimmten Reihenfolge

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.[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   aus einer Grundgesamtheit von   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   aus einer Grundgesamtheit von   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

Bearbeiten
 
Alle 60 Variationen ohne Wiederholung von 3 aus 5 Objekten

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
 
Ein Beispiel für eine injektive Funktion. Bei dieser Darstellung ist die Definitionsmenge   und die Zielmenge  . Die Funktionswerte sind  . Diese injektive Funktion stellt eine Variation ohne Wiederholung mit   und   dar.

Jede Variation ohne Wiederholung kann formal als injektive Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.[7] 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.[8]

Variation mit Wiederholung

Bearbeiten
 
Alle 125 Variationen mit Wiederholung von 3 aus 5 Objekten

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

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
 
Ein Beispiel für eine Funktion. Bei dieser Darstellung ist die Definitionsmenge   und die Zielmenge  . Die Funktionswerte sind  . Diese Funktion stellt eine Variation mit (möglicher) Wiederholung mit   und   dar.

Jede Variation mit (möglicher) Wiederholung kann formal als Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.[7] 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

Einzelnachweise

Bearbeiten
  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