Mathematik
Kombinatorik-Rechner
Wähle die Art der Zusammenstellung, gib n und k ein und erhalte die exakte Anzahl samt der auf deine Zahlen angewandten Formel. Wenn du unsicher bist: Die Anleitung unten geht von den zwei Fragen aus, die zur Entscheidung genügen.
Welche Formel: Zwei Fragen genügen
Die Kombinatorik kennt sechs leicht zu verwechselnde Formeln, doch zur Auswahl der richtigen braucht es nur zwei Fragen. Erstens: Zählt die Reihenfolge? Ergibt das Vertauschen zweier Elemente eine andere Zusammenstellung — eine Rangliste, ein Passwort, eine Folge —, dann zählt die Reihenfolge und man spricht von Variationen oder Permutationen; ergibt es keine — eine Mannschaft, ein Kartenblatt, eine Zahlenmenge —, spricht man von Kombinationen. Zweitens: Darf ein Element mehrfach auftreten? Wenn ja, nimmt man die Variante „mit Wiederholung".
Der Unterschied zwischen Variationen und Permutationen liegt nur darin, wie viele Elemente man nimmt: Permutationen sind der Fall, in dem alle n Elemente verwendet werden, also Variationen mit k = n, und die Anzahl reduziert sich auf n!. Kombinationen erhält man dagegen aus den Variationen durch Division durch k!, die Anzahl der Umordnungen der k gewählten Elemente: Genau diese Division bedeutet „die Reihenfolge zählt nicht".
Der Binomialkoeffizient „n über k" ist keine andere Formel als die Kombinationen: Es ist dieselbe unter anderem Namen und in anderer Schreibweise. Er tritt bei der Entwicklung einer Binomialpotenz und im Pascalschen Dreieck auf, wo jede Zeile die Kombinationen von n Elementen zu 0, 1, 2 … n aufzählt. Er erklärt auch, warum C(n; k) = C(n; n−k) gilt: Auszuwählen, wer dabei ist, heißt auszuwählen, wer draußen bleibt.
Häufige Fehler
- Variationen verwenden, wo Kombinationen nötig sind: Fragt die Aufgabe nach Mannschaften zu 5 aus 12 Spielern, zählt die Reihenfolge nicht und die Antwort lautet C(12; 5) = 792, nicht V(12; 5) = 95.040. Die zweite Zahl ist 120-mal größer, also 5!.
- Vergessen, dass k bei Variationen mit Wiederholung größer als n sein darf: Aus 26 Buchstaben entstehen Passwörter mit 8 Zeichen, und 26⁸ ist vollkommen definiert. Die Bedingung k ≤ n gilt nur ohne Wiederholung.
- Die Anagramme eines Wortes mit wiederholten Buchstaben als einfache Fakultät berechnen: MATHEMATIK hat 10 Buchstaben, aber 10! zählt die Vertauschungen der beiden M als verschieden. Man muss durch 2!·2!·2! teilen.
Häufige Fragen
Was ist der Unterschied zwischen Variationen und Kombinationen?
Bei Variationen zählt die Reihenfolge, bei Kombinationen nicht. Aus drei Buchstaben A, B, C gibt es sechs Variationen zu zwei Elementen (AB, BA, AC, CA, BC, CB) und drei Kombinationen (AB, AC, BC). Kombinationen erhält man aus Variationen durch Division durch k!.
Warum ist 0! gleich 1?
Weil es genau eine Art gibt, null Objekte anzuordnen: nichts tun. Die Konvention ist nicht willkürlich, sie hält alle Formeln stimmig: Ohne sie wären C(n; 0) und C(n; n) nicht gleich 1, wie sie sein müssen.
Wie berechnet man den Binomialkoeffizienten?
„n über k" ist n! / (k! · (n−k)!) und dasselbe wie die Kombinationen von n Elementen zu je k. Es gilt die Symmetrie C(n; k) = C(n; n−k), die die Rechnung oft halbiert.
Wie viele Anagramme hat ein Wort mit wiederholten Buchstaben?
Man teilt die Fakultät der Gesamtzahl der Buchstaben durch das Produkt der Fakultäten der Wiederholungen. MATHEMATIK hat 10 Buchstaben mit je zwei M, A und T: 10!/(2!·2!·2!) = 453.600.
Wie diese Berechnung funktioniert
Fakultät: n! = n·(n−1)·…·2·1, mit 0! = 1. Permutationen von n Elementen: Pₙ = n!. Permutationen mit Wiederholung, bei n₁, n₂, … fach wiederholten Elementen: n!/(n₁!·n₂!·…). Variationen ohne Wiederholung: V(n; k) = n!/(n−k)! = n·(n−1)·…·(n−k+1), erfordert k ≤ n. Variationen mit Wiederholung: V′(n; k) = nᵏ, ohne Bedingung zwischen n und k. Kombinationen, also Binomialkoeffizient: C(n; k) = n!/(k!·(n−k)!), mit C(n; k) = C(n; n−k). Kombinationen mit Wiederholung: C′(n; k) = C(n+k−1; k). Gerechnet wird in exakter Ganzzahlarithmetik, weil die Zahlen jenseits von 20! die Genauigkeit von Gleitkommazahlen übersteigen.