Variation (Kombinatorik)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine Variation (von lateinisch variatio ‚Veränderung‘) oder geordnete Stichprobe 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 | Quelltext bearbeiten]

Eine Variation oder geordnete Stichprobe 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.[1]

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

Variation ohne Wiederholung[Bearbeiten | Quelltext bearbeiten]

Alle 60 Variationen ohne Wiederholung von 3 aus 5 Objekten

Anzahl[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Die Menge

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

Beispiele[Bearbeiten | Quelltext bearbeiten]

Urne mit Kugeln[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.[4] 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.[5]

Variation mit Wiederholung[Bearbeiten | Quelltext bearbeiten]

Alle 125 Variationen mit Wiederholung von 3 aus 5 Objekten

Anzahl[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Würfel[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.[4] 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 | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b 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.
  4. a b Klaus Sutner, Carnegie Mellon University: CDM Combinatorics
  5. Maria Axenovich, Torsten Ueckerdt, Jonathan Rollin, Stefan Walzer, Karlsruher Institut für Technologie: Lecture Notes - Combinatorics, Seite 27 und 28