Variation (Kombinatorik)

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

Eine Variation oder geordnete Stichprobe ist eine Auswahl von k Objekten aus einer Menge von n Objekten, wobei die Reihenfolge der Auswahl eine Rolle spielt. Werden alle verfügbaren Objekte ausgewählt, gilt also k=n, so spricht man statt von einer Variation von einer Permutation, spielt bei der Auswahl der Objekte die Reihenfolge keine Rolle von einer 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.

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 dann „k-Permutationen“ (k-permutations) genannt.

Variation ohne Wiederholung

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

Anzahl

Bei einer Variation ohne Wiederholung sollen k von n Objekten (mit k\leq n) auf k verfügbare Plätze platziert werden, wobei jedes Objekt nur höchstens einen Platz einnehmen darf. Es gibt für den ersten Platz n mögliche Objekte, für den zweiten Platz n-1 Objekte usw. bis zum k-ten Platz, für den es noch n-k+1 mögliche Objekte gibt. Insgesamt gibt es also

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 n^{\underline{k}} und (n)_k, die fallende Faktorielle genannt werden. Mit n! wird die Fakultät von n bezeichnet.

Mengendarstellung

Die Menge

\{ (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 n Objekten zur Klasse k“ und hat die oben angegebene Anzahl von Elementen.

Beispiele

Variation mit Wiederholung

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

Anzahl

Bei einer Variation mit Wiederholung werden aus n Objekten k Objekte unter Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können. Nachdem jedes der n Objekte auf jedem der k Plätze der Auswahl erscheinen kann, gibt es demzufolge

\underbrace{n \cdot \dotsc \cdot n}_{k\text{-mal}} = n^k

mögliche Anordnungen.

Mengendarstellung

Die Menge

\{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 n Objekten zur Klasse k“. Sie ist das k-fache kartesische Produkt der Menge \{1, 2, \dotsc, n\} mit sich selbst und hat die oben angegebene Anzahl von Elementen.

Beispiele

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 02.02. 2022