Kombination ohne Wiederholung

Bei der Kombination ohne Wiederholung (auch Kombination ohne Zurücklegen) geht es darum, k Objekte aus einer Gesamtheit von n zu entnehmen, ohne das entnommene Objekt vor dem nächsten Zug wieder zurückzulegen. Lotto ist hierfür ein Beispiel. Aus einer Gesamtheit von 49 Kugeln werden sechs gezogen und die gezogene Kugel kommt nicht zurück in die Trommel. Die Reihenfolge der gezogenen Kugeln ist auch irrelevant.

Definition

Entnimmt man aus einer Gesamtheit von n Objekten k Objekte, so gibt die folgende Formel an, auf wie viele verschiedene Arten dieser Objekte gezogen werden können:

$ \Large{ \dfrac{n!}{k!\left ( n-k \right )!}\;\;=\;\;\displaystyle\binom{n}{k} } $

Die Formel für Kombination ohne Wiederholung entspricht dem Binomialkoeffizienten.

Beispiel mit Erklärung

Ein bekannter Modedesigner will für seine neueste Kreation zwei verschiedene Stoffe miteinander kombinieren. Zur Auswahl hat er insgesamt vier Materialien: Leder, Seide, Baumwolle und Kaschmirwolle. Wie viele verschiedene Möglichkeiten hat er, zwei verschiedene Stoffe aus den vier ihm zur Verfügung stehenden auszuwählen?

Leder & Seide	Seide & Leder	Baumwolle & Leder	Kaschmirwolle & Leder
Leder & Baumwolle	Seide & Baumwolle	Baumwolle & Seide	Kaschmirwolle & Seide
Leder & Kaschmirwolle	Seide & Kaschmirwolle	Baumwolle & Kaschmirwolle	Kaschmirwolle & Baumwolle

Insgesamt gibt es 12 verschiedene Kombinationen (ohne gleiche Stoffe wie Leder & Leder). Da allerdings die Reihenfolge unwichtig ist, müssen wir von der Liste noch die Hälfte streichen. Am Ende haben wir damit 6 verschiedene Kombinationen aus zwei Stoffen.

Erklärung

Schauen wir uns mal an, wie die Formel für „Kombination ohne Zurücklegen“ genau funktioniert:

$ \Large{ \dfrac{\obrace[{\footnotesize\text{{alle Permutationen}}}]{n!}}{\ubrace[\text{\footnotesize{Doppelte entfernen}}]{k!\vphantom{\left ( n-k \right )!}}\cdot\ubrace[\text{\footnotesize{Auswahl von $n$}}]{\left ( n-k \right )!}} } $

n!

Mit n! berechnen wir alle Permutationen – also die Anzahl der möglichen Anordnungen von allen vier Stoffen, wobei die Reihenfolge nicht vernachlässigt wird. Damit erhalten wir eine Liste mit 24 Möglichkeiten:

Leder, Seide, Baumwolle, Kaschmirwolle	Leder, Seide, Kaschmirwolle, Baumwolle	Leder, Baumwolle, Kaschmirwolle, Seide	Seide, Baumwolle, Kaschmirwolle, Leder
Seide, Leder, Baumwolle, Kaschmirwolle	Seide, Leder, Kaschmirwolle, Baumwolle	Baumwolle, Leder, Kaschmirwolle, Seide	Baumwolle, Seide, Kaschmirwolle, Leder
Leder, Baumwolle, Seide, Kaschmirwolle	Leder, Kaschmirwolle, Seide, Baumwolle	Leder, Kaschmirwolle, Baumwolle, Seide	Seide, Kaschmirwolle, Baumwolle, Leder
Baumwolle, Leder, Seide, Kaschmirwolle	Kaschmirwolle, Leder, Seide, Baumwolle	Kaschmirwolle, Leder, Baumwolle, Seide	Kaschmirwolle, Seide, Baumwolle, Leder
Seide, Baumwolle, Leder, Kaschmirwolle	Seide, Kaschmirwolle, Leder, Baumwolle	Baumwolle, Kaschmirwolle, Leder, Seide	Baumwolle, Kaschmirwolle, Seide, Leder
Baumwolle, Seide, Leder, Kaschmirwolle	Kaschmirwolle, Seide, Leder, Baumwolle	Kaschmirwolle, Baumwolle, Leder, Seide	Kaschmirwolle, Baumwolle, Seide, Leder

(Für weitere Informationen hierzu, bitte auch die Artikel Permutation und Fakultät lesen.)

(n – k)!

Wir benötigen allerdings nur zwei der vier Stoffe. Indem wir durch (n – k)! teilen, wählen wir zwei aus den vier Stoffen aus:

Leder & Seide	Seide & Leder	Baumwolle & Leder	Kaschmirwolle & Leder
Leder & Baumwolle	Seide & Baumwolle	Baumwolle & Seide	Kaschmirwolle & Seide
Leder & Kaschmirwolle	Seide & Kaschmirwolle	Baumwolle & Kaschmirwolle	Kaschmirwolle & Baumwolle

Da bei dieser Zusammenstellung die Reihenfolge noch von Bedeutung ist, entspricht dies der Variante ohne Wiederholung.

k!

Ob Leder & Seide oder Seide & Leder – es macht für uns keinen Unterschied, deshalb müssen wir noch alle doppelten Werte entfernen. Unser Endergebnis ist schließlich:

Leder & Seide	Seide & Leder	Baumwolle & Leder	Kaschmirwolle & Leder
Leder & Baumwolle	Seide & Baumwolle	Baumwolle & Seide	Kaschmirwolle & Seide
Leder & Kaschmirwolle	Seide & Kaschmirwolle	Baumwolle & Kaschmirwolle	Kaschmirwolle & Baumwolle

Rechner für Kombination ohne Wiederholung

$ \large {\color{gray}{ n\in \mathbb{N} }} $

$ \large {\color{gray}{ k\in \mathbb{N},\;\; n\geq k }} $

Ergebnis

$$\large\binom{n}{k} \,=\, \frac{n!}{k!\,(n-k)!} \,=\, $$