Variation (Kombinatorik) - LinkFang.de





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 [math]k[/math] Objekten aus einer Menge von [math]n[/math] Objekten, wobei die Reihenfolge der Auswahl eine Rolle spielt. Werden alle verfügbaren Objekte ausgewählt, gilt also [math]k=n[/math], 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

Anzahl

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

[math]n\cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}[/math]

mögliche Anordnungen. Für diese Zahl existieren auch die Notationen [math]n^{\underline{k}}[/math] und [math](n)_k[/math], die fallende Faktorielle genannt werden. Mit [math]n![/math] wird die Fakultät von [math]n[/math] bezeichnet.

Mengendarstellung

Die Menge

[math]\{ (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 \}[/math]

ist die „Menge aller Variationen ohne Wiederholung von [math]n[/math] Objekten zur Klasse [math]k[/math]“ und hat die oben angegebene Anzahl von Elementen.

Beispiele

  • Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal ohne Zurücklegen gezogen wird, sind [math]5 \cdot 4 \cdot 3 = 60[/math] 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 [math]5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120[/math] Möglichkeiten, also die Zahl der Permutationen aller fünf Kugeln.

Variation mit Wiederholung

Anzahl

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

[math]\underbrace{n \cdot \dotsc \cdot n}_{k\text{-mal}} = n^k[/math]

mögliche Anordnungen.

Mengendarstellung

Die Menge

[math]\{1, 2, \dotsc, n\}^k = \bigl\{(x_1, x_2, \dotsc, x_{k}) \mid x_{i} \in \{1, 2, \dotsc, n\} \bigl\}[/math]

ist die „Menge aller Variationen mit Wiederholung von [math]n[/math] Objekten zur Klasse [math]k[/math]“. Sie ist das [math]k[/math]-fache kartesische Produkt der Menge [math]\{1, 2, \dotsc, n\}[/math] mit sich selbst und hat die oben angegebene Anzahl von Elementen.

Beispiele

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

Literatur

Einzelnachweise

  1. 1,0 1,1 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.

Kategorien: Kombinatorik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Variation (Kombinatorik) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.