Variation (Kombinatorik)

Anzahl

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

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

Mengendarstellung

Die Menge

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

Beispiele

Darstellung als injektive Funktion

Jede Variation ohne Wiederholung kann formal als injektive Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.^[7] Die Definitionsmenge ${\displaystyle X:=\{x_{1},x_{2},\ldots ,x_{k}\}}$ hat ${\displaystyle k}$ Elemente und die Zielmenge ${\displaystyle Y:=\{y_{1},y_{2},\ldots ,y_{n}\}}$ hat ${\displaystyle n}$ Elemente. Dann stellt jede injektive Funktion ${\displaystyle f\colon \,X\to Y}$ eine Variation ohne Wiederholung dar.

Für ${\displaystyle f(x_{1})}$ gibt es ${\displaystyle n}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$. Für ${\displaystyle f(x_{2})}$ gibt es dann noch ${\displaystyle n-1}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1})}$. Für ${\displaystyle f(x_{3})}$ gibt es dann noch ${\displaystyle n-2}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1}),f(x_{2})}$. Diese Argumentation lässt sich fortsetzen. Für ${\displaystyle f(x_{k})}$ gibt es schließlich noch ${\displaystyle n-k+1}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ mit Ausnahme von ${\displaystyle f(x_{1}),f(x_{2}),\ldots ,f(x_{k-1})}$. Daraus ergeben sich insgesamt ${\displaystyle n\cdot (n-1)\cdot \ldots \cdot (n-k+1)={\frac {n!}{(n-k)!}}}$ mögliche injektive Funktionen ${\displaystyle f\colon \,X\to Y}$, was der Anzahl der Variationen ohne Wiederholung entspricht.^[8]

Anzahl

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

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

mögliche Anordnungen.

Mengendarstellung

Die Menge

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

Beispiele

Darstellung als Funktion

Jede Variation mit (möglicher) Wiederholung kann formal als Funktion mit einer endlichen Definitionsmenge und einer endlichen Zielmenge aufgefasst werden.^[7] Die Definitionsmenge ${\displaystyle X:=\{x_{1},x_{2},\ldots ,x_{k}\}}$ hat ${\displaystyle k}$ Elemente und die Zielmenge ${\displaystyle Y:=\{y_{1},y_{2},\ldots ,y_{n}\}}$ hat ${\displaystyle n}$ Elemente. Dann stellt jede Funktion ${\displaystyle f\colon \,X\to Y}$ eine Variation mit (möglicher) Wiederholung dar.

Für ${\displaystyle f(x_{1})}$ gibt es ${\displaystyle n}$ mögliche Funktionswerte, nämlich ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$. Für ${\displaystyle f(x_{2})}$ gibt es ebenfalls diese ${\displaystyle n}$ möglichen Funktionswerte. Diese Argumentation lässt sich fortsetzen. Auch für ${\displaystyle f(x_{k})}$ gibt es schließlich diese ${\displaystyle n}$ möglichen Funktionswerte. Daraus ergeben sich insgesamt ${\displaystyle \underbrace {n\cdot \dotsc \cdot n} _{k{\text{-mal}}}=n^{k}}$ mögliche Funktionen ${\displaystyle f\colon \,X\to Y}$, was der Anzahl der Variationen mit Wiederholung entspricht.