Variation (Kombinatorik)

Grundidee und Abgrenzung

Eine Variation ist in der Kombinatorik eine Auswahl von Objekten aus einer Menge, bei der die Reihenfolge der ausgewählten Objekte berücksichtigt wird. Man wählt k Objekte aus einer Menge von n Objekten aus. Die Anzahl möglicher Variationen zu bestimmen, ist eine Standardaufgabe der abzählenden Kombinatorik.

Der Unterschied zu einer Kombination besteht darin, dass bei einer Kombination die Reihenfolge nicht berücksichtigt wird. Werden alle verfügbaren Objekte ausgewählt, also k = n, spricht man statt von einer Variation von einer Permutation.

Es gibt zwei Hauptfälle: Bei einer Variation ohne Wiederholung darf jedes Objekt nur einmal auftreten. Bei einer Variation mit Wiederholung können Objekte mehrfach ausgewählt werden. Im Urnenmodell entspricht das einer Ziehung ohne Zurücklegen beziehungsweise mit Zurücklegen, jeweils mit Berücksichtigung der Reihenfolge.

Eine Variation ohne Wiederholung ist eine Stichprobe ohne Zurücklegen des Umfangs k aus einer Grundgesamtheit von n Elementen, wobei die Reihenfolge berücksichtigt wird, kurz eine geordnete Auswahl ohne Zurücklegen. Eine Variation mit Wiederholung ist entsprechend eine Stichprobe mit Zurücklegen des Umfangs k aus einer Grundgesamtheit von n Elementen, ebenfalls mit Berücksichtigung der Reihenfolge, kurz eine geordnete Auswahl mit Zurücklegen.

Nicht verwechselt werden darf die geordnete Auswahl mit einer geordneten Stichprobe. Eine geordnete Stichprobe entsteht, wenn die Werte einer Stichprobe nach ihrer Größe angeordnet werden. In der Literatur werden Begriffe teilweise anders zusammengefasst: Manchmal werden Variationen als Kombinationen mit Berücksichtigung der Reihenfolge bezeichnet; im englischen Sprachgebrauch werden Variationen auch mit Permutationen zusammengefasst und partial permutations oder k-permutations genannt.

Ohne Wiederholung

Bei einer Variation ohne Wiederholung werden k von n Objekten mit k ≤ n auf k Plätze verteilt, wobei jedes Objekt höchstens einmal vorkommen darf. Für den ersten Platz gibt es n Möglichkeiten, für den zweiten n − 1 Möglichkeiten und so weiter bis zum k-ten Platz, für den noch n − k + 1 Möglichkeiten bleiben.

Die Anzahl der Variationen ohne Wiederholung ist daher

n · (n − 1) · … · (n − k + 1) = n! / (n − k)!

Diese Zahl wird auch mit n^{\underline{k}} oder (n)_k bezeichnet und heißt fallende Faktorielle. Mit n! wird die Fakultät von n bezeichnet.

Als Menge lassen sich alle Variationen ohne Wiederholung von n Objekten zur Klasse k durch Tupel darstellen:

{(x₁, x₂, …, x_k) | x_i ∈ {1, 2, …, n}, x_i ≠ x_j für i ≠ j}

Die Bedingung x_i ≠ x_j bedeutet, dass kein Objekt zweimal vorkommt.

Beispiele ohne Wiederholung

Bei einer Urne mit 5 nummerierten Kugeln, aus der 3-mal ohne Zurücklegen gezogen wird, gibt es für die erste Kugel 5 Möglichkeiten, für die zweite 4 und für die dritte 3. Wenn die Reihenfolge der gezogenen Kugeln berücksichtigt wird, gibt es insgesamt 5 · 4 · 3 = 60 Auswahlmöglichkeiten. Werden alle 5 Kugeln gezogen, erhält man 5 · 4 · 3 · 2 · 1 = 5! = 120 Möglichkeiten, also die Anzahl der Permutationen aller 5 Kugeln.

Bei 9 Personen und 4 Sitzplätzen in einem Zugabteil kann der erste Sitzplatz von 9 Personen, der zweite von 8, der dritte von 7 und der vierte von 6 Personen besetzt werden. Daraus ergeben sich 9 · 8 · 7 · 6 = 3024 mögliche Sitzordnungen, wenn nur die belegten Plätze betrachtet werden. Umgekehrt ergeben sich bei 4 Personen und 9 Sitzplätzen im Flugzeugabteil ebenfalls 9 · 8 · 7 · 6 = 3024 Sitzordnungen, wenn jede Person genau einen Platz bekommt und jeder Platz höchstens einmal besetzt wird.

Bei einem Team mit 7 verschiedenen Positionen und 10 möglichen Personen gibt es für die erste Position 10 Möglichkeiten und für die siebte noch 4. Insgesamt entstehen 10 · 9 · 8 · 7 · 6 · 5 · 4 = 604800 Zuordnungsmöglichkeiten. Solche Aufstellungen können als Variationen ohne Wiederholung angesehen werden, wenn jede Person für jede Position zur Verfügung steht. In der Praxis ist die reine Anzahl aber oft wenig relevant, weil nicht jede Person jede Position übernehmen kann und Rückennummern nicht immer verschiedenen Positionen entsprechen.

Mit Wiederholung

Bei einer Variation mit Wiederholung werden aus n Objekten k Objekte ausgewählt, wobei die Reihenfolge zählt und Objekte mehrfach vorkommen dürfen. Auf jedem der k Plätze kann jedes der n Objekte stehen. Deshalb gibt es

n · … · n = n^k

mögliche Anordnungen, wobei der Faktor n insgesamt k-mal vorkommt.

Als Menge werden alle Variationen mit Wiederholung von n Objekten zur Klasse k so dargestellt:

{1, 2, …, n}^k = {(x₁, x₂, …, x_k) | x_i ∈ {1, 2, …, n}}

Das ist das k-fache kartesische Produkt der Menge {1, 2, …, n} mit sich selbst. Anders als bei der Variation ohne Wiederholung gibt es keine Bedingung, dass die Einträge verschieden sein müssen.

Beispiele mit Wiederholung

Beim viermaligen Werfen eines Spielwürfels mit den Augenzahlen 1 bis 6 gibt es bei jedem Wurf 6 mögliche Ergebnisse. Für 4 Würfe entstehen daher 6 · 6 · 6 · 6 = 6^4 = 1296 mögliche Ergebnisfolgen.

Bei einer Urne mit 5 nummerierten Kugeln, aus der 3-mal mit Zurücklegen gezogen wird, gibt es bei jeder Ziehung wieder 5 Möglichkeiten. Wenn die Reihenfolge betrachtet wird, ergeben sich 5 · 5 · 5 = 5^3 = 125 verschiedene Auswahlmöglichkeiten.

Eine 4-stellige PIN oder ein Zahlenschloss mit 4 Ringen und je 10 Ziffern hat 10^4 = 10000 verschiedene Variationen. Dazu gehören die Zahlen 0000 bis 9999, also auch Zahlen, die mit 0 beginnen. In der Digitaltechnik bestehen Binärzahlen nur aus den Ziffern 0 und 1. Mit k Bits entstehen 2^k verschiedene Variationen; eine 4-stellige Binärzahl kodiert 2^4 = 16 Zustände.

Allgemein ist die Anzahl der natürlichen Zahlen mit n Ziffern im Stellenwertsystem der Basis b gleich b^n, wenn Zahlen mit führender 0 mitgezählt werden. Bei einer digitalen Rastergrafik mit 1280 × 720 Pixeln gibt es 1280 · 720 = 921600 Pixel. Im RGB-Farbraum hat jedes Pixel 3 Farbkanäle mit je 8 Bit, also pro Farbkanal 2^8 = 256 Zustände und pro Pixel 256^3 = 16777216 mögliche Werte. Daraus ergeben sich 16777216^921600 mögliche digitale Rastergrafiken, wenn die Farbwerte verlustfrei komprimiert und gespeichert werden.

Funktionale Darstellung

Variationen lassen sich auch mit Funktionen beschreiben. Eine Funktion ordnet jedem Element einer Definitionsmenge genau ein Element einer Zielmenge zu. Die Definitionsmenge X = {x₁, x₂, …, x_k} hat k Elemente, die Zielmenge Y = {y₁, y₂, …, y_n} hat n Elemente.

Eine Variation mit Wiederholung entspricht einer beliebigen Funktion f: X → Y. Für jedes f(x_i) stehen immer alle n Funktionswerte y₁, y₂, …, y_n zur Verfügung. Daher gibt es insgesamt n^k solche Funktionen.

Eine Variation ohne Wiederholung entspricht einer injektiven Funktion f: X → Y. Injektiv bedeutet: Verschiedene Elemente der Definitionsmenge bekommen verschiedene Funktionswerte. Für f(x₁) gibt es n Möglichkeiten, für f(x₂) noch n − 1, für f(x₃) noch n − 2 und so weiter. Für f(x_k) bleiben n − k + 1 Möglichkeiten. Insgesamt gibt es deshalb n · (n − 1) · … · (n − k + 1) = n! / (n − k)! injektive Funktionen, also genau die Anzahl der Variationen ohne Wiederholung.