Variation (Kombinatorik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine Variation (von lateinisch variatio „Veränderung“) oder geordnete Stichprobe ist in der Kombinatorik eine Auswahl von Objekten 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. 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 eine Rolle spielt. Werden alle verfügbaren Objekte ausgewählt, gilt also , 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 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 dann „k-Permutationen“ (k-permutations) genannt.[3]

Variation ohne Wiederholung[Bearbeiten | Quelltext bearbeiten]

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

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]

  • Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal ohne Zurücklegen gezogen wird, sind 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 Möglichkeiten, also die Zahl der Permutationen aller fünf Kugeln.

Variation mit Wiederholung[Bearbeiten | Quelltext bearbeiten]

Alle 125 Variationen mit Wiederholung von drei aus fünf Zahlen

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]

  • Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal mit Zurücklegen gezogen wird, dann sind verschiedene Auswahlen möglich.
  • Bei einer vierstelligen PIN oder einem Zahlenschloss mit vier Ringen und je zehn Ziffern gibt es insgesamt verschiedene Variationen (0000–9999).
  • In der Digitaltechnik verwendete Binärzahlen bestehen nur aus den beiden Ziffern und . Mit einer Anordnung von solchen Ziffern können dementsprechend verschiedene Variationen entstehen. Eine vierstellige Binärzahl kodiert beispielsweise verschiedene Zustände.

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.