Kombinationen

Zu den typischen kombinatorischen Fragestellungen gehören solche, bei denen nicht mehr (wie bei Permutationen) alle zur Verfügung stehenden Elemente angeordnet werden sollen, sondern eine Auswahl (von k aus n Elementen) erfolgt.

Werden dabei alle möglichen Reihenfolgen der Elemente betrachtet und unterschieden, so spricht man von Variationen, wird die Reihenfolge nicht berücksichtigt von Kombinationen.
(Der Begriff Kombination wird mitunter auch als Oberbegriff für Variation und Kombination verwendet.)

Variationen

Jede mögliche Anordnung von je k aus n Elementen, bei der die Reihenfolge berücksichtigt wird, heißt Variation (von n Elementen zur k-ten Klasse).

Sind die n Elemente verschieden, so gilt für die Anzahl der möglichen Anordnungen (der Variationen ohne Wiederholung):
$V_n^k=n\cdot \left(n-1\right)\cdot \mathrm{...}\cdot \left[n-\left(k-1\right)\right]\left(n,k\in N;n\ge k\right)$
bzw. unter Verwendung der Fakultätsschreibweise
$V_n^k=\frac{n!}{\left(n-k\right)!}\left(n,k\in \mathbb{N};n\ge k\right)$

Beispiel 1:
Wie viele Variationen von fünf Elementen zur zweiten Klasse gibt es?
Lösung:
$\begin{array}{l}abbacadaea\\ acbccbdbeb\\ adbdcddcec\\ aebecedeed\\ V_5^2=5\cdot 4=20\end{array}$

Für den Fall, dass auch Wiederholungen (von Elementen) zugelassen sein sollen, erhöht sich die Zahl der möglichen Anordnungen (im Beispiel 1 um 5 auf 25).

Allgemein gilt für die Anzahl der Variationen mit Wiederholung:
${}^{w}V{}_k^n=n^k$

Beispiel 2:
Im Online-Wettbewerb zum Schülerlexikon werden 15 Fragen gestellt und pro Frage jeweils fünf Antworten zur Auswahl vorgegeben. Wie viele verschiedene Möglichkeiten der Beantwortung (des Ankreuzens des „Tipp-Scheins“) gibt es?
Lösung:
${}^{w}V{}_5^{15}=5^{15}\approx \mathrm{3,05}\cdot {10}^{10}$

Anmerkung: Bei Variationen mit Wiederholung von Elementen ist eine Einschränkung auf den Fall $k\le n$ nicht erforderlich, es kann auch $k>n$ gelten.

Beispiel 3:
Wie viele Variationen mit Wiederholung von zwei Elementen zur fünften Klasse gibt es?
Lösung:
${}^{w}V{}_2^5=2^5=32$

Kombinationen

Jede mögliche Anordnung von je k aus n Elementen, bei der die Reihenfolge der Elemente nicht berücksichtigt wird, heißt Kombination (von n Elementen zur k-ten Klasse).

Für Kombinationen ohne Wiederholung (von Elementen) gilt:
$C_n^k=\frac{n!}{\left(n-k\right)!\cdot k!}=\left(\begin{array}{c}n\\ k\end{array}\right)\left(n,k\in \mathbb{N};n\ge k\right)$

(Im Vergleich zu Variationen reduziert sich die Anzahl, da diejenigen Anordnungen, die sich nur durch Permutation der einzelnen Elemente unterscheiden, gleich sind.)
Anmerkung: Der Ausdruck $\left(\begin{array}{c}n\\ k\end{array}\right)$ wird auch als Binomialkoeffizient bezeichnet.

Beispiel 4:
Wie viele verschiedene Möglichkeiten gibt es, aus zehn Zahlen drei auszuwählen?
Lösung:
$C_{10}^3=\frac{10!}{7!\cdot 3!}=120$

Für die Anzahl der Kombinationen mit Wiederholung (von Elementen) gilt:
${}^{w}C{}_n^k=\left(\begin{array}{c}n+k-1\\ k\end{array}\right)(n,k\in \mathbb{N};n>1;k\text{ beliebig)}$

Beispiel 5:
Wie oft lassen sich die Elemente a, b, c und d zur zweiten Klasse kombinieren?
Lösung:
$\begin{array}{l}aaabacadbb\\ bcbdcccddd\\ {}^{w}C{}_4^2=\left(\begin{array}{c}5\\ 2\end{array}\right)=10\end{array}$

Anmerkung: ab und ba stellen (beispielsweise) die gleiche Kombination dar.