Kombinationen, Variationen & Fakultät berechnen
Wie viele Möglichkeiten, Dinge auszuwählen, zu ordnen oder anzuordnen? Die Kombinatorik antwortet mit drei Werkzeugen: der Fakultät, den Variationen (die Reihenfolge zählt) und den Kombinationen (die Reihenfolge ist gleichgültig). Geben Sie die Gesamtzahl n und die gewählte Zahl k an, mit oder ohne Wiederholung.
Die Schlüsselfrage: Zählt die Reihenfolge? Ein Podium (Gold, Silber, Bronze) ist eine Variation — die Reihenfolge unterscheidet die Ergebnisse. Eine Kartenhand oder Lottozahlen sind eine Kombination — nur die Menge zählt, nicht die Ziehungsreihenfolge.
Eingaben
Ergebnis
- C(49, 6) 13.983.816
| n (verfügbare Elemente) | 49 |
| k (gewählte Elemente) | 6 |
| Kombinationen ohne Wiederholung C(n, k) | 13.983.816 |
| Kombinationen mit Wiederholung C(n+k−1, k) | 25.827.165 |
C(n, k) = n! / [ k! · (n − k)! ]
Reihenfolge oder Menge: die eine Frage, die alles entscheidet
Die Kombinatorik steht auf einem Baustein, der Fakultät. n! zählt die Wege, n verschiedene Dinge anzuordnen: n Plätze für den Ersten, n − 1 für den Zweiten, weiter bis 1. 0! setzen wir auf 1, sonst bricht jede Formel am Rand zusammen. Variationen und Kombinationen sind nur Fakultäten, einmal gekürzt.
V(n, k) = n! / (n − k)! · C(n, k) = V(n, k) / k! = n! / [k! · (n − k)!]
Die Schlüsselfrage bleibt: Zählt die Reihenfolge? Podium, Passwort, PIN — ja, dann Variation. Tippfeld, Kartenblatt, Ausschussmenge — nein, dann Kombination. Mit anderen Worten: Ist (A, B) dasselbe Ergebnis wie (B, A)? Wenn ja, durch k! teilen. Wenn nein, die Variation stehen lassen. Der Rest ist Algebra.
Die Permutation ist der Sonderfall k = n: alle n Elemente, alle Reihenfolgen, n! = V(n, n). Ein Kartenspiel mischen, eine Namensliste permutieren, die Sitzordnung einer Kommission — dasselbe Zählproblem. C(n, n) ist 1: Es gibt nur eine Menge, die alles enthält.
Variation: die Reihenfolge zählt (nPk)
Eine Variation ohne Wiederholung V(n, k) — auf dem Taschenrechner oft nPr oder nPk — zählt geordnete k-Tupel aus n verschiedenen Elementen, jedes höchstens einmal. Podium von 3 aus 8 Läufern: 8 × 7 × 6 = 336. Gold-Silber-Bronze ist ein anderes Ergebnis als Bronze-Silber-Gold. Ranglisten, Zieleinläufe, die ersten k Plätze einer Auslosung: alles Variationen.
V(n, k) = n × (n − 1) × … × (n − k + 1)
Die Produktform spart das volle n! und das (n − k)!. Gerade deshalb rechnet der Rechner so und nicht über zwei Fakultäten, die unterwegs überlaufen. nPk auf dem Casio, nPr auf dem TI, Vnk im deutschen Formelheft: drei Namen, eine Zahl. Verwechseln Sie sie nicht mit nCk — das ist die Kombination, um den Faktor k! kleiner.
Beispielsweise ein 5-stelliges Codewort aus 26 Buchstaben, jeder Buchstabe höchstens einmal: V(26, 5) = 26 × 25 × 24 × 23 × 22 = 7.893.600. Dürfen Buchstaben wiederholt werden, sind wir nicht mehr hier, sondern bei nk.
Kombination: die Reihenfolge ist gleichgültig (nCk)
Eine Kombination C(n, k) zählt Teilmengen. Die Ziehungsreihenfolge fällt weg; wir teilen die Variation durch k!, die Zahl der Permutationen der gezogenen k Elemente. Auf dem Rechner nCr oder nCk, im Heft „n über k“, der Binomialkoeffizient. Fünf Karten aus 52: C(52, 5) = 2.598.960 Blätter. Ob Herz-As zuerst kam oder zuletzt, das Blatt ist dasselbe.
C(n, k) = (n über k) = n! / [k! · (n − k)!] · C(n, k) = C(n, n − k)
Die Symmetrie C(n, k) = C(n, n − k) nützt dem Algorithmus: 6 aus 49 zu wählen ist dasselbe Zählproblem wie 43 liegen zu lassen. Der Rechner nutzt das intern, er nimmt das kleinere von k und n − k. Übrigens ist C(n, 0) = 1 und C(n, 1) = n — die leere Auswahl und die Einzelwahl, Randfälle, an denen Formeln sterben, wenn 0! nicht 1 ist.
Hingegen darf C(n, k) nicht als Wahrscheinlichkeit gelesen werden. C ist eine Anzahl. Die Chance, dass ein bestimmtes Blatt fällt, ist 1/C nur, wenn jedes Blatt gleich wahrscheinlich ist. Beim Mischen ja, beim gezinkten Spiel nein. Zählen und Wahrscheinlichkeiten sind Nachbarn, nicht Zwillinge.
Mit oder ohne Zurücklegen
Ohne Zurücklegen (ohne Wiederholung): Jedes Element höchstens einmal. Urne, Kugel raus, bleibt draußen. Klassische V(n, k) und C(n, k). Lotto, Poker, Podium, eine Kommission aus der Belegschaft.
Mit Zurücklegen (mit Wiederholung): Die Kugel wandert zurück, ein Element darf erneut vorkommen. Die geordnete Version ist schlicht nk — k Stellen, n Zeichen, Wiederholung erlaubt. Ein 4-stelliger PIN aus Ziffern 0–9: 104 = 10.000, von 0000 bis 9999. Die ungeordnete Version, Kombinationen mit Wiederholung, ist C(n + k − 1, k): Multimengen. Drei Kugeln aus fünf Farben, Farben dürfen mehrfach, die Reihenfolge egal — das ist dieses C, nicht das klassische.
- Variation ohne Wiederholung — V(n, k), geordnet, ohne Zurücklegen.
- Variation mit Wiederholung — nk, geordnet, mit Zurücklegen (PIN, Passwort mit wiederholbaren Zeichen).
- Kombination ohne Wiederholung — C(n, k), ungeordnet, ohne Zurücklegen (Lotto, Pokerhand).
- Kombination mit Wiederholung — C(n + k − 1, k), ungeordnet, mit Zurücklegen.
Klar: Die vier Kästchen zu verwechseln ist der Standardfehler. Ein Passwort, in dem derselbe Buchstabe zweimal stehen darf, ist nk, keine Variation ohne Wiederholung. Ein Lottotipp, in dem keine Zahl doppelt vorkommt und die Reihenfolge auf dem Schein egal ist, ist C, nicht V. Wer V(49, 6) statt C(49, 6) nimmt, liegt um den Faktor 720 daneben — 6!.
Lotto 6 aus 49
Beim deutschen Lotto „6 aus 49“ zählt die Ziehungsreihenfolge nicht, Zahlen wiederholen sich nicht. Die Zahl der Tipps ist C(49, 6) = 13.983.816. Ein Fünfer ohne Superzahl ist eine andere Klasse; der Sechser selbst steht bei 1 zu rund 14 Millionen, sofern jede Kombination gleich wahrscheinlich gezogen wird. n = 49, k = 6, Modus Kombinationen: Der Rechner muss genau diese 13.983.816 liefern.
Ein Tipp kostet einen Einsatz, 14 Millionen Tipps wären 14 Millionen Einsätze. Die Superzahl (0–9) hängt als zehnfacher Faktor hinterher, sie ändert C(49, 6) nicht, sie multipliziert die Chance auf den Jackpot. Jedenfalls ist „ich spiele die Geburtstage“ keine Strategie: Geburtstage liegen zwischen 1 und 31, die Ziehung nicht. Geteilt wird der Gewinn häufiger, die Trefferchance steigt nicht.
Eurojackpot und ähnliche Spiele sind Produkte zweier Kombinationen (Fünf aus fünfzig mal zwei aus zwölf, je nach Regeljahr). Erst jede Urne für sich zählen, dann multiplizieren. Das ist immer noch Kombinatorik, keine Glockenkurve. Eine Normalverteilung auf 6-aus-49 zu legen, wäre die falsche Familie.
Passwörter, PINs und der Zeichenvorrat
Ein PIN mit 4 Ziffern, Wiederholung erlaubt, Reihenfolge zählt: 104 = 10.000. Ohne führende Nullen wären es 9×10³ = 9.000 — eine andere Zählung, ein anderer Türcode. Acht Zeichen aus 62 alphanumerischen (26+26+10), Wiederholung erlaubt: 628 ≈ 2,18×1014. Dasselbe ohne Wiederholung: V(62, 8), etwas kleiner, immer noch astronomisch. Die Wiederholung ist hier der Normalfall; Menschen wählen „Passwort1“, Maschinen dürfen Zeichen doppelt.
Sonderzeichen vergrößern n, nicht k. 95 druckbare ASCII-Zeichen, Länge 8, mit Wiederholung: 958. Länge 12 statt 8 wirkt stärker als ein paar Extra-Zeichen, weil der Exponent k ist. Unter dem Strich: Erst n (Vorrat) und k (Länge) festlegen, dann entscheiden, ob Zeichen sich wiederholen dürfen. Erst danach die Formel. Ein Passwortmanager würfelt nk; eine „zufällige“ Phrase aus sieben deutschen Wörtern eines 5.000-Wörter-Schatzes ist 50007, sofern die Wörter unabhängig und mit Wiederholung gezogen werden.
Heutzutage scheitern die meisten Konten nicht an 628, sondern an Wiederverwendung und Wörterbuch. Die Kombinatorik zählt den Suchraum. Sie sagt nichts darüber, welchen Winkel ein Angreifer zuerst durchsucht.
Poker: fünf Karten aus 52
Ein 52er-Blatt, fünf Karten, Reihenfolge egal, keine Karte doppelt: C(52, 5) = 2.598.960 Hände. Das ist die Grundgesamtheit der klassischen Zählung mit fünf Karten. Royal Flush gibt es vier (eine Farbe je). Vierling: 624. Full House: 3.744. Die Wahrscheinlichkeiten sind diese Anzahlen durch 2.598.960, nicht „ungefähr 1 %“, wenn die Klausur die genaue Klasse will.
- Royal Flush — 4 Hände, C(52, 5) im Nenner → 1 zu 649.740.
- Vierling — 624 Hände → rund 1 zu 4.165.
- Full House — 3.744 Hände → rund 1 zu 694.
Texas Hold’em mischt Gemeinschaftskarten dazu; die Zählung wird eine andere, weil zwei Lochkarten plus fünf offene Karten nicht dasselbe Urnenmodell sind wie fünf Karten in die Hand. Ansonsten gilt weiter: erst Kombination (ungeordnete Menge), dann erst die Wertung der Hand. Wer Variationen zählt, multipliziert jede Hand mit 5! = 120 und muss denselben Faktor im Nenner wieder kürzen. Erst recht in der Klausur: Das Kürzen vergessen, und die Wahrscheinlichkeit ist 120-mal zu klein.
170! und der Overflow
Fakultäten wachsen schneller als der Intuition lieb ist. 10! = 3.628.800, noch handlich. 20! ≈ 2,43×1018. 70! hat schon 101 Stellen. 170! ≈ 7,257×10306 — das liegt knapp unter der Obergrenze einer IEEE-754-Doppelgenauigkeit (rund 1,80×10308). 171! läuft über, der Rechner sieht „Unendlich“. Oben steht die Schranke 170, nicht aus Pädagogik, aus Gleitkomma-Physik.
C(n, k) und V(n, k) berechnet diese Seite als laufendes Produkt, nicht als Quotient zweier fertiger Fakultäten. 50! / (6!·44!) wäre ein Quotient zweier Riesen; das gekürzte Produkt (49×48×47×46×45×44)/(6×5×4×3×2×1) bleibt zahm und liefert 13.983.816 exakt. Kurzum: Die Formel im Heft darf n! zeigen, der Code darf das nicht wörtlich nachbauen.
Stirlings Näherung n! ≈ √(2πn)·(n/e)n gibt die Größenordnung, wenn 170 überschritten ist und niemand eine Big-Integer-Bibliothek anwirft. Für den Alltag dieser Seite reicht: Jenseits von 170! erscheint eine Meldung, kein Ziffernsalat. Große, noch darstellbare Ergebnisse erscheinen in wissenschaftlicher Schreibweise, mit Komma als Dezimaltrennzeichen.
n! wächst schwindelerregend. 170! streift die Gleitkomma-Grenze, 171! ist für diesen Rechner unendlich. Vergleichen Sie C und V nicht über den Umweg zweier voller Fakultäten, wenn n über 170 liegt — das Produkt in den gekürzten Formeln bleibt gültig, der naive Quotient n! / k! nicht.