Kombinationsrechner

In der Kombinatorik gibt es verschiedene Strategien, um die Anzahl der Möglichkeiten zu bestimmen, Objekte aus einer bestimmten Menge auszuwählen. Auf wie viele Arten können wir r Elemente aus n Möglichkeiten auswählen? Das hängt primär davon ab, ob die Reihenfolge der Auswahl eine Rolle spielt und ob sich Elemente wiederholen dürfen.

Die Anzahl der Möglichkeiten, r Elemente ohne Beachtung der Reihenfolge aus n Möglichkeiten auszuwählen, wird als Kombination bezeichnet und oft als C(n, r) geschrieben. Dieser Wert ist in der Mathematik auch als Binomialkoeffizient bekannt. Mit diesem benutzerfreundlichen Kombinationsrechner können Sie schnell und exakt ermitteln, wie viele Kombinationen von r Objekten aus einer Gesamtmenge von n Objekten möglich sind.

So funktioniert der Kombinationsrechner

Für eine gegebene Menge von Objekten gibt es eine bestimmte Anzahl von Wegen, einige oder alle von ihnen nach einer bestimmten Spezifikation auszuwählen oder anzuordnen. Dieser Rechner ermittelt die Anzahl der Möglichkeiten zur Auswahl von r Objekten aus einer Menge von n Objekten – und zwar für den Fall "Ziehen ohne Zurücklegen" (ohne Wiederholung), wenn die genaue Reihenfolge irrelevant ist. Für die Berechnung benötigt das Tool lediglich zwei Eingaben:

• n = Gesamtanzahl der verschiedenen Objekte, aus denen gewählt werden kann
• r = Anzahl der auszuwählenden Objekte (Stellen)

Ein wesentliches mathematisches Kriterium für die Dateneingabe in den Kombinationsrechner lautet:

$$0 ≤ r ≤ n$$

Wenn Sie für r einen Wert eingeben, der größer ist als n, gibt das System automatisch folgende Fehlermeldung aus:

"Bitte geben Sie 0 ≤ r ≤ n ein".

Das Grundprinzip des Zählens

Das grundlegende Zählprinzip der Kombinatorik hilft uns dabei, systematisch Wege zur Bewältigung verschiedener Aufgaben zu finden. Es gibt zwei essenzielle Zählregeln, die Sie kennen sollten.

Die Summenregel

Wenn eine erste Aufgabe auf m Arten erledigt werden kann und eine zweite Aufgabe auf n Arten, beide Aufgaben aber nicht gleichzeitig oder nacheinander ausführbar sind (Entweder-oder-Prinzip), dann lässt sich die Gesamtzahl der möglichen Wege als (m + n) berechnen.

Die Produktregel

Wenn eine erste Aufgabe auf m Arten erledigt werden kann und eine zweite Aufgabe auf n Arten und beide Aufgaben gleichzeitig oder direkt nacheinander ausgeführt werden, dann gibt es (m × n) Kombinationsmöglichkeiten.

Anwendungsbeispiele

In einer Cafeteria werden 3 Arten von Kuchen und 4 Arten von Getränken verkauft. Das Angebot umfasst Apfel-, Erdbeer- und Blaubeerkuchen sowie Orangen-, Trauben-, Kirsch- und Ananassaft. Sowohl ein Getränk als auch ein Stück Kuchen kosten jeweils 2 $. Sie haben genau 2 $ dabei und keinen Cent mehr. Sie müssen sich also für entweder Kuchen oder Saft entscheiden. Nach der Summenregel haben Sie folglich 3 + 4 = 7 Möglichkeiten, Ihre Wahl zu treffen.

Angenommen, Sie möchten die Anzahl der möglichen Ergebnisse berechnen, wenn Sie eine Münze und einen Würfel gleichzeitig werfen. Die Anzahl der Ergebnisse beim Münzwurf ist 2 (Kopf oder Zahl). Beim Würfeln gibt es 6 mögliche Ergebnisse. Da beide Aktionen unabhängig voneinander und gleichzeitig stattfinden, gibt es gemäß der Produktregel 2 × 6 = 12 verschiedene Kombinationsmöglichkeiten für dieses Experiment.

Wenn Sie 2 Karten aus einem klassischen Kartendeck mit 52 Karten ziehen möchten (ohne sie wieder zurückzulegen), haben Sie exakt 52 Möglichkeiten für das Ziehen der ersten Karte. Für die zweite Karte verbleiben noch 51 Möglichkeiten. Die Anzahl der Möglichkeiten, zwei bestimmte Karten nacheinander zu ziehen, beträgt nach der Produktregel also 52 × 51 = 2.652.

Ergebnisräume (Stichprobenräume)

Ein Ergebnisraum (oft auch Stichprobenraum genannt) ist die Menge aller möglichen Ergebnisse eines Zufallsexperiments. Er wird in der Mathematik meist mit dem Großbuchstaben S (oder Omega $\Omega$) bezeichnet. Der Ergebnisraum für das gleichzeitige Werfen einer englischen Münze (H = Head/Kopf, T = Tail/Zahl) und eines Würfels lautet:

S = {{H,1}, {H,2}, {H,3}, {H,4}, {H,5}, {H,6}, {T,1}, {T,2}, {T,3}, {T,4}, {T,5}, {T,6}}

Es gibt genau zwölf mögliche Ausgänge. Die Zählprinzipien der Kombinatorik erlauben es uns, die exakte Anzahl der Experimentier-Möglichkeiten zu berechnen, ohne den gesamten Ergebnisraum mühsam per Hand auflisten zu müssen.

Kombinationen berechnen

Die Anzahl der Möglichkeiten, r sich nicht wiederholende Elemente aus n Möglichkeiten auszuwählen, wobei die Reihenfolge der Ziehung irrelevant ist, wird als Kombination bezeichnet. Die Kombination von Objekten wird mathematisch als C(n, r) ausgedrückt. Sie ist identisch mit dem Binomialkoeffizienten. Die offizielle Kombinationsformel lautet:

$$C(n,r)=\frac{n!}{r!(n-r)!}$$

Das Ausrufezeichen (!) hinter einer Zahl oder Variablen steht für die Fakultät. Die Fakultät $n!$ ist das Produkt aller natürlichen Zahlen von 1 bis $n$. Zum Beispiel ist die Fakultät der Zahl 2 schlicht 1 × 2. Die Fakultät von 3 ist 1 × 2 × 3. Die Fakultät von 4 ist 1 × 2 × 3 × 4. Die Fakultät von 5 ist 1 × 2 × 3 × 4 × 5 – und so weiter. Wichtig: Die Fakultät kann nur für nicht-negative ganze Zahlen berechnet werden.

Die beiden wichtigsten Merkmale bei der Berechnung von Kombinationen mit dieser Formel sind: Die Wiederholung von Objekten ist nicht erlaubt (Ziehen ohne Zurücklegen) und die Reihenfolge der Anordnung spielt absolut keine Rolle.

Beispiel 1

Angenommen, Sie haben eine Menge bestehend aus vier Zahlen:

{1, 2, 3, 4}

Wie viele Möglichkeiten gibt es, zwei Elemente aus dieser Menge zu kombinieren, wenn dasselbe Element in einem Paar nicht wiederholt werden darf?

Wenn die Reihenfolge der Elemente wichtig wäre, bekämen wir Gruppen, die durch Permutationen gebildet werden:

(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)

Da bei Kombinationen die Reihenfolge jedoch nicht von Bedeutung ist, fallen Duplikate (wie 1,2 und 2,1) weg. Wir erhalten folgende Gruppen:

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

Es gibt folglich 6 mögliche Kombinationen. Sie können die Formel verwenden, um dieses Ergebnis mathematisch abzusichern. Für dieses Beispiel gilt: $n=4$, $r=2$. Eingesetzt in die Formel folgt daraus:

$$C(4,2)=\frac{4!}{2!(4-2)!}=\frac{4!}{2!2!}=\frac{4 × 3 × 2 × 1}{(2× 1)(2× 1)}=\frac{24}{4}=6$$

Genau dieses Ergebnis liefert Ihnen auch unser Kombinationsrechner in Sekundenbruchteilen.

Beispiel 2

Wie lauten die Kombinationen der Buchstaben A, B, C und D in einer 3er-Gruppe? Es gäbe 24 mögliche Permutationen, falls die Reihenfolge wichtig wäre. Da in der kombinatorischen Zählung die Reihenfolge jedoch irrelevant ist, ist in der folgenden Tabelle nur die erste Zeile wirklich maßgeblich. Es gibt dementsprechend exakt 4 mögliche Kombinationen.

Anstatt alle möglichen Anordnungen aufwendig aufzulisten, berechnen wir die Anzahl der Kombinationen (bei denen die Reihenfolge keine Rolle spielt) ganz einfach mit der Kombinationsformel. In diesem Fall gibt es n=4 Objekte, und wir entnehmen jeweils r=3. Daraus folgt:

$$C\left(n,r\right)=C\left(4,3\right)=\frac{4!}{\left(4-3\right)!3!}=\frac{4!}{1!3!}=4$$

Permutationen

Die Permutation definiert die Anzahl der Möglichkeiten, Objekte anzuordnen, wenn die Reihenfolge der Objekte zwingend wichtig ist. Die Formel für die Permutation bei der Auswahl von r Objekten aus einer Liste von n Objekten lautet wie folgt:

$$P\left(n,r\right)=\frac{n!}{\left(n-r\right)!}$$

Die beiden Hauptmerkmale der Berechnung von Permutationen mit dieser Formel sind, dass die Wiederholung von Objekten weiterhin nicht erlaubt ist, die exakte Reihenfolge der Objekte jedoch den entscheidenden Unterschied macht.

Beispiel 3

Angenommen, es gibt 4 Bewerber in einem Vorstellungsgespräch. Die Aufgabe des Auswahlausschusses ist es, die Bewerber in eine Rangfolge von Platz 1 bis 4 zu bringen. Hier sind die Möglichkeiten für die Platzvergabe:

• 1. Platz – es gibt 4 mögliche Kandidaten
• 2. Platz – es gibt noch 3 mögliche Kandidaten
• 3. Platz – es gibt noch 2 mögliche Kandidaten
• 4. Platz – es bleibt nur noch 1 Kandidat übrig

Die Produktregel liefert uns die Gesamtzahl der möglichen Rangfolgen, nämlich 4 × 3 × 2 × 1 = 24, was genau dem Wert der Fakultät 4! entspricht. Angenommen, die Kandidaten heißen:

{A, B, C, D}

Der Ergebnisraum dieses Problems, der alle 24 möglichen Permutationen darstellt, sieht wie folgt aus:

Auch hier gilt: Anstatt alle möglichen Anordnungen wie in der obigen Tabelle mühselig aufzulisten, lässt sich das Ergebnis bequem über die Permutationsformel berechnen. Für das obige Beispiel haben wir n = 4 Objekte, und wir vergeben r = 4 Platzierungen gleichzeitig. Daraus folgt:

$$P\left(n,r\right)=P\left(4,4\right)=\frac{4!}{\left(4-4\right)!}=\frac{4!}{0!}=24$$ (Hinweis: Die Fakultät von Null ($0!$) ist in der Mathematik als 1 definiert.)

Der Unterschied zwischen Kombinationen und Permutationen

Der zentrale Unterschied für die Praxis lässt sich in einem simplen Satz zusammenfassen: Bei Kombinationen ist die Reihenfolge der ausgewählten Elemente völlig unbedeutend, während bei Permutationen die genaue Reihenfolge der Elemente von entscheidender Wichtigkeit ist.