Kombinatorik-Rechner
n und k eintragen, Fall wählen: Zählt die Reihenfolge, darf sich etwas wiederholen? Der Rechner nennt Formel und Ergebnis.
Möglichkeiten berechnen
Reihenfolge zählt: Variation, egal: Kombination, alle anordnen: Permutation.
Beispiel: 6 aus 49 ohne Reihenfolge: 13.983.816
So funktioniert der Kombinatorik-Rechner
Der Kombinatorik-Rechner zählt, wie viele Möglichkeiten es gibt, k Dinge aus n auszuwählen oder n Dinge anzuordnen. Die fünf klassischen Fälle sind alle enthalten: die Kombination ohne Wiederholung (k aus n, Reihenfolge egal, der Lottofall), die Kombination mit Wiederholung (Eiskugeln aus Sorten), die Variation ohne Wiederholung (Reihenfolge zählt, Podium), die Variation mit Wiederholung (PIN, Zahlenschloss) und die Permutation (alle n anordnen, Sitzordnung). Sie wählen den Fall, tragen n und k ein und bekommen die Formel, das Ergebnis, die Chance für eine bestimmte Auswahl und zum Vergleich die Werte der anderen Fälle mit denselben Zahlen. Sehr große Ergebnisse zeigt der Rechner in Zehnerpotenzen.
Merksatz: Zwei Fragen entscheiden den Fall. Zählt die Reihenfolge? Dann Variation oder Permutation, sonst Kombination. Darf etwas mehrfach vorkommen? Dann "mit Wiederholung". Eselsbrücke für den Binomialkoeffizienten: "n über k" ist die Zahl der Lottotipps, wenn k Kugeln aus n gezogen werden.
Drei Beispiele:
- Lotto 6 aus 49: (49 über 6) = 49! / (6! × 43!) = 13.983.816. Die Chance für einen bestimmten Tipp ist 1 zu 13.983.816. Beim Eurojackpot mit 5 aus 50 sind es 2.118.760 Fünferkombinationen, noch ohne die Eurozahlen.
- Podium bei 10 Läufern: Gold, Silber, Bronze sind geordnet, also 10 × 9 × 8 = 720 Möglichkeiten. Bei 20 Startern sind es 6.840, ohne Reihenfolge nur 1.140 Dreiergruppen.
- Vierstellige PIN: 10^4 = 10.000. Ein Passwort aus vier Kleinbuchstaben hat 26^4 = 456.976 Varianten, acht Personen am Tisch 8! = 40.320 Sitzordnungen.
Formeln: Permutation n!, Variation ohne Wiederholung n! / (n - k)!, Variation mit Wiederholung n^k, Kombination ohne Wiederholung (n über k) = n! / (k! × (n - k)!), Kombination mit Wiederholung (n + k - 1 über k). Die Fakultät allein rechnet der Fakultät-Rechner, die Gewinnklassen im Lotto der Lotto-Chancen-Rechner.
Wissenswertes zum Thema
Die zwei Fragen, die den Fall bestimmen
Kombinatorik wirkt unübersichtlich, weil fünf Formeln mit ähnlichen Namen nebeneinanderstehen. Dabei entscheiden nur zwei Fragen. Erstens: Zählt die Reihenfolge? Beim Podium ja, denn Gold für Anna und Silber für Ben ist ein anderes Ergebnis als umgekehrt. Beim Lotto nein, denn die Kugeln landen sortiert auf dem Schein. Zweitens: Ist Wiederholung erlaubt? Beim Zahlenschloss ja, 1-1-1-1 ist eine gültige Stellung. Beim Lotto nein, jede Kugel wird nur einmal gezogen. Daraus ergibt sich die Vierfeldertafel: Reihenfolge zählt und Wiederholung erlaubt ist die Variation mit Wiederholung n^k; Reihenfolge zählt ohne Wiederholung ist die Variation ohne Wiederholung n!/(n - k)!; Reihenfolge egal ohne Wiederholung die Kombination "n über k"; Reihenfolge egal mit Wiederholung die Kombination mit Wiederholung "n + k - 1 über k". Die Permutation n! ist der Sonderfall der Variation ohne Wiederholung mit k = n, wenn also alle Objekte angeordnet werden. Wer in der Aufgabe diese beiden Fragen beantwortet, hat die Formel gefunden; der Rechner zeigt zur Kontrolle alle Fälle mit denselben Zahlen nebeneinander.
Der Binomialkoeffizient und das Pascalsche Dreieck
"n über k" heißt Binomialkoeffizient, weil die Zahlen als Koeffizienten beim Ausmultiplizieren von (a + b)^n auftauchen. Im Pascalschen Dreieck steht in Zeile n an Stelle k genau (n über k), und jede Zahl ist die Summe der beiden darüber. Zeile 4 lautet 1, 4, 6, 4, 1: Aus vier Dingen lassen sich auf sechs Arten zwei auswählen. Zwei Eigenschaften sparen Rechenarbeit. Die Symmetrie (n über k) = (n über n - k): 6 aus 49 auszuwählen ist dasselbe wie 43 Nieten auszuwählen. Und die Kürzung: Statt 49! auszurechnen, was eine Zahl mit 63 Stellen ist, rechnet man 49 × 48 × 47 × 46 × 45 × 44 / 720 = 13.983.816. So arbeitet auch der Rechner intern, deshalb liefert er bis n = 170 exakte Werte, bevor die Gleitkommadarstellung an ihre Grenze stößt. Die Kombination mit Wiederholung lässt sich auf denselben Koeffizienten zurückführen: 3 Kugeln aus 5 Eissorten sind (7 über 3) = 35 Becher, weil man sich die Auswahl als Folge von Kugeln und Trennstrichen zwischen den Sorten vorstellt.
Große Zahlen und das Gefühl dafür
Kombinatorische Zahlen wachsen schneller, als die Intuition mitkommt. Eine Skatkarte aus 32 Blatt ist eine von 32, ein Skatblatt mit zehn Karten aber eines von 64.512.240. Zehn Personen lassen sich auf 3.628.800 Arten in eine Reihe stellen, zwanzig schon auf 2,43 × 10^18, mehr als Sekunden seit dem Urknall. Ein gut gemischtes Kartenspiel mit 52 Blatt hat 52! ≈ 8 × 10^67 Reihenfolgen; es ist praktisch sicher, dass die Reihenfolge nach dem Mischen noch nie zuvor existiert hat. Bei Passwörtern zählt der Rechner die Variationen mit Wiederholung: vier Ziffern 10.000, sechs Ziffern eine Million, acht Zeichen aus 62 Buchstaben und Ziffern 2,18 × 10^14. Die Zahl der Möglichkeiten sagt noch nichts über die Wahrscheinlichkeit einer einzelnen, wenn nicht alle gleich wahrscheinlich sind: 1234 wird häufiger gewählt als 7391, was Angreifer wissen. Für faire Zufallsexperimente gilt aber: Die Chance auf eine bestimmte Auswahl ist eins durch die Zahl der Möglichkeiten, und genau das zeigt der Rechner als "1 zu".
Ein Stück Geschichte
Das Zählen von Anordnungen ist älter als die Wahrscheinlichkeitsrechnung. Im indischen Medizintext Sushruta Samhita, der etwa auf das 6. Jahrhundert vor Christus zurückgeht, werden die 63 Kombinationen aus sechs Geschmacksrichtungen aufgezählt. Der Mathematiker Bhaskara II. gab im 12. Jahrhundert in seiner "Lilavati" Formeln für Permutationen und Kombinationen an. Das Zahlendreieck, das wir nach Blaise Pascal benennen, kannten chinesische Gelehrte um Jia Xian im 11. Jahrhundert und Yang Hui im 13.; Pascal veröffentlichte 1665 seinen "Traité du triangle arithmétique" und verband die Zahlen systematisch mit Glücksspielfragen. Jakob Bernoulli ordnete in der "Ars Conjectandi" von 1713 Permutationen und Kombinationen als eigenes Gebiet, und Leonhard Euler führte 1778 eine Schreibweise für den Binomialkoeffizienten ein. Die heute übliche Klammer "n über k" stammt von Andreas von Ettingshausen aus dem Jahr 1826. Das deutsche Lotto "6 aus 49" wurde 1955 eingeführt; seine 13.983.816 Tipps sind seither das bekannteste Kombinatorikbeispiel im Land.
Praktische Tipps
Formulieren Sie die Aufgabe als Auswahlvorgang, bevor Sie rechnen: Was wird aus wie vielen ausgewählt, und ändert ein Tausch zweier Auswahlen das Ergebnis? Wenn Sie unsicher sind, zählen Sie ein winziges Beispiel von Hand, etwa 2 aus 3, und vergleichen mit den Formeln. Bei "mindestens"-Fragen in Auswahlaufgaben hilft oft das Gegenteil: Die Zahl der Hände ohne Ass ist leichter als die mit mindestens einem Ass. Für Wahrscheinlichkeiten teilen Sie günstige durch mögliche Kombinationen, beides zählt dieser Rechner; die Rechnung selbst übernimmt dann der Wahrscheinlichkeitsrechner. Für k Treffer in n Ziehungen mit fester Trefferwahrscheinlichkeit stecken die Binomialkoeffizienten im Binomialverteilung-Rechner. Und wenn Ergebnisse als Zehnerpotenz erscheinen, ist das kein Fehler, sondern eine Zahl mit mehr als 15 Stellen.
Häufige Fragen
Was ist der Unterschied zwischen Permutation, Variation und Kombination?
Permutation ordnet alle n Objekte an (n!). Variation wählt k aus n mit Reihenfolge (n!/(n-k)! ohne, n^k mit Wiederholung). Kombination wählt k aus n ohne Reihenfolge ("n über k" ohne, "n+k-1 über k" mit Wiederholung). Die Fragen "zählt die Reihenfolge?" und "ist Wiederholung erlaubt?" entscheiden.
Wie rechnet man "n über k"?
n! / (k! × (n - k)!), kürzer als Produkt n × (n-1) × … × (n-k+1) geteilt durch k!. Für 49 über 6: 49 × 48 × 47 × 46 × 45 × 44 / 720 = 13.983.816. Der Rechner zeigt die Formel mit Ihren Zahlen an.
Wie viele Möglichkeiten gibt es beim Lotto 6 aus 49?
13.983.816 verschiedene Tipps, die Chance auf sechs Richtige mit einem Tipp ist also 1 zu 13.983.816. Mit der Superzahl von 0 bis 9 wird daraus 1 zu 139.838.160.
Wie viele vierstellige PINs gibt es?
10^4 = 10.000, weil an jeder der vier Stellen zehn Ziffern möglich sind und sich Ziffern wiederholen dürfen. Das ist eine Variation mit Wiederholung. Sechs Stellen ergeben eine Million.
Was ist eine Kombination mit Wiederholung?
Eine Auswahl ohne Reihenfolge, bei der dasselbe Objekt mehrfach vorkommen darf, etwa drei Kugeln aus fünf Eissorten: (5 + 3 - 1 über 3) = (7 über 3) = 35 verschiedene Becher. Ohne Wiederholung wären es nur 10.
Warum zeigt der Rechner manchmal eine Zehnerpotenz?
Ab etwa 15 Stellen stellt der Rechner das Ergebnis als Zahl mal Zehnerpotenz dar, zum Beispiel 2,433 × 10^18 für 20!. Die Zahl ist dann gerundet, die Größenordnung stimmt exakt. Bis n = 170 rechnet der Rechner, darüber übersteigt n! den Zahlenbereich.
Wie viele Sitzordnungen gibt es für 8 Personen?
8! = 40.320 an einer Bank. An einem runden Tisch, an dem nur die Nachbarschaft zählt, sind es (8 - 1)! = 5.040, weil Drehungen dieselbe Ordnung ergeben.
Was hat Kombinatorik mit Wahrscheinlichkeit zu tun?
Bei gleich wahrscheinlichen Ergebnissen ist die Wahrscheinlichkeit gleich günstige durch mögliche Fälle, und beides sind kombinatorische Anzahlen. Die Chance auf ein bestimmtes Skatblatt ist 1 zu 64.512.240, weil es so viele Zehnerauswahlen aus 32 Karten gibt.
Was ist der Binomialkoeffizient?
Die Zahl der Möglichkeiten, k Elemente aus n ohne Reihenfolge und ohne Wiederholung auszuwählen, geschrieben n über k und berechnet als n! ÷ (k! · (n - k)!). 49 über 6 ergibt 13.983.816, die Zahl der Lottotipps; 5 über 2 ergibt 10. Das ist die Kombination ohne Wiederholung im Rechner.