Binomialkoeffizient-Rechner: n über k, Fakultät und Kombinatorik

Der Binomialkoeffizient n über k zählt Auswahlen ohne Reihenfolge

Wer aus n verschiedenen Elementen k Stück auswählt und sich nur für die Auswahl interessiert, nicht für die Reihenfolge, landet beim Binomialkoeffizienten. Die Formel lautet n über k = n! / (k! · (n − k)!). Das Ausrufezeichen steht für die Fakultät: n! = n · (n − 1) · … · 2 · 1. Der Rechner arbeitet mit exakten Ganzzahlen, Rundungsfehler gibt es deshalb auch bei sehr großen Ergebnissen nicht.

49 über 6 berechnen: der gekürzte Rechenweg

Die Formel mit drei Fakultäten sieht aufwendig aus, weil 49! eine Zahl mit 63 Stellen ist. Kürzen macht die Rechnung handlich: 49! / 43! lässt nur die sechs Faktoren von 49 bis 44 übrig.

1. Ansatz: 49 über 6 = 49! / (6! · 43!)
2. Gekürzt: (49 · 48 · 47 · 46 · 45 · 44) / (6 · 5 · 4 · 3 · 2 · 1)
3. Zähler 10.068.347.520, Nenner 720
4. Ergebnis: 10.068.347.520 / 720 = 13.983.816

Der Zähler allein, 10.068.347.520, ist die Zahl der Ziehungen mit Reihenfolge. Das Teilen durch 6! = 720 entfernt alle Anordnungen derselben sechs Zahlen. Was diese Zahl für die Gewinnchancen bedeutet, rechnet der Wahrscheinlichkeitsrechner für alle neun Lotto-Gewinnklassen vor.

n über k Tabelle: häufige Werte zum Nachschlagen

Fakultät-Rechner: wie schnell n! wächst

Die Fakultät wächst schneller als jede Potenz. Schon 10! übersteigt drei Millionen, 70! ist die erste Fakultät mit mehr als 100 Stellen.

52! ist die Zahl der möglichen Reihenfolgen eines Kartenspiels mit 52 Blatt. Gründlich gemischt liegt ein Stapel deshalb mit an Sicherheit grenzender Wahrscheinlichkeit in einer Reihenfolge, die es noch nie gegeben hat. Viele Schultaschenrechner zeigen höchstens 69! an, weil 70! über 10^100 liegt und zwei Stellen im Exponenten nicht mehr reichen. Wie sich eine Fakultät in Primfaktoren zerlegt, zeigt der Primfaktorzerlegung-Rechner für kleinere Werte.

Kombinatorik-Rechner mit Urnenmodell: welche Formel passt

Das Urnenmodell ordnet jede Zählaufgabe nach zwei Fragen: Wird zurückgelegt, und zählt die Reihenfolge? Daraus entstehen vier Fälle. Die Tabelle zeigt sie für n = 10 Kugeln und k = 3 Züge sowie für n = 49 und k = 6.

Ein fünfter Fall ist die Permutation ohne Wiederholung: alle n Elemente in eine Reihenfolge bringen, also n!. Für zehn Elemente sind das 3.628.800 Anordnungen.

Permutation mit Wiederholung: die Buchstaben von MISSISSIPPI

Kommen gleiche Elemente mehrfach vor, ergeben Vertauschungen untereinander keine neue Anordnung. Die Formel teilt deshalb n! durch die Fakultäten der Gruppengrößen. MISSISSIPPI hat 11 Buchstaben: einmal M, viermal I, viermal S, zweimal P. Im Rechner geben Sie die Gruppen als 1, 4, 4, 2 ein und erhalten 11! / (1! · 4! · 4! · 2!) = 39.916.800 / 1.152 = 34.650 verschiedene Buchstabenfolgen. Für ANNAS mit den Gruppen 2, 2, 1 (zweimal A, zweimal N, einmal S) ergeben sich 5! / (2! · 2! · 1!) = 30 Anordnungen.

Pascalsches Dreieck und Symmetrie von n über k

Jede Zahl im Pascalschen Dreieck ist die Summe der beiden Zahlen darüber, und jede Zeile n enthält die Werte n über 0 bis n über n. Zeile 5 lautet 1, 5, 10, 10, 5, 1, Zeile 6 lautet 1, 6, 15, 20, 15, 6, 1. Daran sieht man die Symmetrie: n über k ist gleich n über (n − k), denn wer k Elemente auswählt, legt zugleich fest, welche n − k übrig bleiben. Der größte Wert einer Zeile steht immer in der Mitte. Die Zeilen liefern zugleich die Vorfaktoren der Binomialverteilung, die der Binomialverteilung-Rechner für beliebige Trefferwahrscheinlichkeiten auswertet.

Praxisbeispiel Kombinatorik: Eisdiele mit zehn Sorten

Eine Eisdiele bietet zehn Sorten an, Sie bestellen drei Kugeln. Mit n = 10 und k = 3 liefert der Rechner alle Varianten auf einmal:

• Drei verschiedene Sorten im Becher, Reihenfolge egal: 10 über 3 = 120 Möglichkeiten.
• Sorten dürfen sich wiederholen, Reihenfolge egal: (12 über 3) = 220 Möglichkeiten. Dreimal Vanille zählt jetzt mit.
• Drei verschiedene Sorten in der Waffel, Reihenfolge von unten nach oben zählt: 720 Möglichkeiten.
• Wiederholung erlaubt, Reihenfolge zählt: 10³ = 1.000 Möglichkeiten, so viele wie bei einem dreistelligen Zahlenschloss.

Plausibilitätsprüfung für n über k

• n über 1 ist immer n, n über 0 und n über n sind immer 1.
• n über 2 ist n · (n − 1) / 2, also die Zahl der Paare. Bei zwölf Personen: 66 Händedrücke.
• Die Kombination ohne Wiederholung ist immer kleiner als die Variation ohne Wiederholung, genau um den Faktor k!.
• Alle Werte einer Zeile des Pascalschen Dreiecks ergeben zusammen 2ⁿ. Zeile 6: 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64.
• Ist k größer als n, ist n über k gleich 0: Aus fünf Elementen lassen sich keine sechs verschiedenen auswählen.

Typische Fehler beim Binomialkoeffizienten

n über k mit n geteilt durch k verwechseln. Die Schreibweise mit runden Klammern erinnert an einen Bruch, ist aber keiner. 10 über 3 ist 120, nicht 3,33.

Reihenfolge übersehen. Wer beim Lotto mit 49 · 48 · 47 · 46 · 45 · 44 rechnet, zählt jede Auswahl 720-mal und landet bei über zehn Milliarden statt knapp 14 Millionen.

Mit Zurücklegen als nᵏ zählen, obwohl die Reihenfolge egal ist. Drei Kugeln aus zehn Sorten mit Wiederholung ergeben 220 Kombinationen, nicht 1.000. Die 1.000 gelten nur, wenn die Reihenfolge zählt.

Fakultäten vollständig ausrechnen. Auf dem Taschenrechner führt 100! / (98! · 2!) zum Überlauf, obwohl das Ergebnis nur 100 · 99 / 2 ist. Kürzen Sie immer zuerst.