Was bedeutet „n über k“?

Der Binomialkoeffizient C(n,k), gesprochen „n über k“, zählt Auswahlen von k Elementen aus einer Menge mit n verschiedenen Elementen, wenn die Reihenfolge keine Rolle spielt und kein Element doppelt gewählt wird. Aus 20 Personen können 38.760 verschiedene Sechsergruppen gebildet werden.

Die Formel lautet n!/(k!(n−k)!). Das Ausrufezeichen bezeichnet die Fakultät: n! ist das Produkt n × (n−1) × … × 2 × 1. Für 20 über 6 würde eine direkte Rechnung 20!, 6! und 14! bilden. Der Rechner nutzt eine kürzere Produktform, um unnötig große Zwischenwerte zu vermeiden.

Die Voraussetzung 0 ≤ k ≤ n ist wesentlich. Eine Auswahl von mehr Elementen als vorhanden ist in der üblichen kombinatorischen Interpretation nicht möglich. Manche mathematische Kontexte definieren den Koeffizienten außerhalb dieses Bereichs als null; diese Eingabeseite verlangt stattdessen die natürliche Auswahlbedingung.

Produktform Schritt für Schritt

Wegen der Symmetrie wird der kleinere Wert von k und n−k verwendet. Für C(20,6) ist das 6. Der Zähler besteht aus sechs aufeinanderfolgenden Faktoren 15 bis 20, der Nenner aus 1 bis 6. Schrittweise wird multipliziert und dividiert, sodass nach jedem Schritt wieder ein exakter ganzzahliger Zwischenwert entsteht.

Die Folge lautet: 1 × 15/1 = 15, dann ×16/2 = 120, ×17/3 = 680, ×18/4 = 3.060, ×19/5 = 11.628 und ×20/6 = 38.760. Diese Methode ist weniger fehleranfällig als das vollständige Ausschreiben von 20!.

Effiziente Formel: C(n,k) = Produkt für i = 1 bis m aus (n − m + i)/i, wobei m = min(k,n−k).

Warum C(n,k) = C(n,n−k)?

Jede Auswahl von k Elementen legt gleichzeitig fest, welche n−k Elemente nicht gewählt wurden. Eine Sechsergruppe aus 20 Personen entspricht eindeutig der Gruppe der 14 nicht ausgewählten Personen. Deshalb gibt es genauso viele Sechser- wie Vierzehnergruppen.

Algebraisch ist die Symmetrie direkt in n!/(k!(n−k)!) sichtbar, weil die beiden Faktoren im Nenner vertauscht werden können. Rechnerisch erlaubt sie, höchstens bis zur Hälfte von n zu multiplizieren. C(100,98) kann als C(100,2) berechnet werden.

Die Symmetrie bedeutet nicht, dass k und n−k in jeder Sachaufgabe dieselbe Rolle spielen. Eine ausgewählte Zweierdelegation hat einen anderen praktischen Zweck als die 98 Nichtdelegierten, auch wenn die Anzahl möglicher Zuordnungen übereinstimmt.

Kombination, Variation und Permutation unterscheiden

Bei einem Vorstand mit Vorsitz, Stellvertretung und Kasse ist die Reihenfolge beziehungsweise Rolle wichtig; C(n,3) reicht nicht. Bei einer dreiköpfigen Arbeitsgruppe ohne Rollen ist der Binomialkoeffizient passend. Schreiben Sie die Bedeutung einer Auswahl auf, bevor Sie eine Formel wählen.

Pascal-Dreieck

Jede innere Zahl des Pascal-Dreiecks ist die Summe der beiden schräg darüberliegenden Zahlen. Das entspricht der Rekursion C(n,k) = C(n−1,k−1) + C(n−1,k). Eine Auswahl enthält entweder ein bestimmtes Element oder nicht. Im ersten Fall müssen noch k−1 aus n−1 gewählt werden, im zweiten k aus n−1.

Der Rechner zeigt die beiden Pascal-Nachbarn des Ergebnisses. Für C(20,6) sind das C(19,5) = 11.628 und C(19,6) = 27.132; ihre Summe ist 38.760. Diese Identität ist eine gute unabhängige Kontrolle.

Binomischer Lehrsatz

Im Ausdruck (a+b)ⁿ stehen die Binomialkoeffizienten als Faktoren der Terme. Der allgemeine Term ist C(n,k)aⁿ⁻ᵏbᵏ. Für (a+b)⁴ lautet die Entwicklung a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴.

Die Summe aller Koeffizienten einer Zeile ist 2ⁿ. Setzt man a = 1 und b = 1, wird (1+1)ⁿ = 2ⁿ. Kombinatorisch ist 2ⁿ zugleich die Zahl aller Teilmengen einer n-elementigen Menge. Jede Teilmenge hat eine bestimmte Größe k, daher ist die Summe von C(n,k) über alle k gleich 2ⁿ.

Die Ausgabe „Anteil der Größe k“ teilt C(n,k) durch 2ⁿ. Bei 20 über 6 machen Sechser-Teilmengen etwa 3,6964 Prozent aller Teilmengen aus.

Genau k Erfolge in der Binomialverteilung

Wenn n unabhängige Versuche jeweils dieselbe Erfolgswahrscheinlichkeit p haben und nur Erfolg oder Misserfolg unterschieden wird, gilt P(X=k) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ. Der Binomialkoeffizient zählt, auf welchen Positionen die k Erfolge liegen können.

Bei n = 20, k = 6 und p = 0,5 ist die Wahrscheinlichkeit C(20,6)/2²⁰, also rund 0,03696 oder 3,696 Prozent. Bei p ungleich 0,5 ist der „Anteil an allen Teilmengen“ nicht mehr identisch mit der Wahrscheinlichkeit, weil Folgen unterschiedlich gewichtet werden.

Unabhängigkeit und konstantes p sind fachliche Annahmen. Ziehen ohne Zurücklegen aus einer kleinen Population ist hypergeometrisch, nicht binomial. Lern- oder Ermüdungseffekte können p zwischen Versuchen verändern.

Randfälle

C(n,0) = 1, weil es genau eine Möglichkeit gibt, nichts auszuwählen: die leere Menge. C(n,n) = 1, weil alle Elemente gewählt werden müssen. C(n,1) = n und C(n,n−1) = n. Diese Werte helfen, eine Implementierung zu testen.

Für n = 0 gilt C(0,0) = 1. Die leere Menge besitzt genau eine Teilmenge, sich selbst. Die Form 0! = 1 ist dabei konsistent. Ein negativer Wert für n oder k gehört nicht zur hier verwendeten Zählaufgabe.

Bei p = 0 ist nur k = 0 möglich; bei p = 1 nur k = n. Der Rechner verarbeitet diese Randfälle über Potenzen, wobei 0⁰ in der passenden Grenzkombination als JavaScript-Wert 1 erscheint. Die Wahrscheinlichkeit bleibt dadurch in diesen diskreten Fällen korrekt.

Große Zahlen und Genauigkeit

Binomialkoeffizienten wachsen sehr schnell. C(52,26) liegt bereits bei rund 4,96 × 10¹⁴, ist aber noch als sichere ganze JavaScript-Zahl darstellbar. Für deutlich größere n können exakte Ganzzahlen den sicheren Bereich überschreiten. Dieses Modul begrenzt n daher auf 52.

Die Grenze ist eine technische Entscheidung, keine mathematische Grenze. Computer-Algebra und Big-Integer-Bibliotheken können viel größere Koeffizienten exakt berechnen. Eine Gleitkommaausgabe in wissenschaftlicher Schreibweise reicht nicht, wenn jede einzelne Kombination exakt gezählt werden muss.

Die Binomialwahrscheinlichkeit kann bei großen n sehr klein werden. Dann sind Logarithmen oder spezialisierte Verteilungsfunktionen numerisch stabiler. Der Rechner ist für überschaubare Lern- und Planungswerte gedacht.

Typische Anwendungen

• Teams oder Ausschüsse ohne Rollen aus einer Gruppe auswählen
• Lotterie-Kombinationen zählen, sofern Reihenfolge und Regeln passen
• Koeffizienten in der Entwicklung von (a+b)ⁿ bestimmen
• Wahrscheinlichkeit genau k Erfolge in unabhängigen Versuchen berechnen
• Teilmengen einer festen Größe zählen
• Identitäten im Pascal-Dreieck prüfen

Wahrscheinlichkeitshinweis: Eine große Zahl möglicher Kombinationen sagt allein nichts über Fairness oder Gewinnchance. Regeln, Anzahl günstiger Ergebnisse und Ziehungsmodell müssen vollständig bekannt sein.

Lotterie-Beispiel ohne Gewinnversprechen

Wer sechs unterschiedliche Zahlen aus 49 ohne Beachtung der Reihenfolge wählt, hat C(49,6) = 13.983.816 mögliche Sechserkombinationen. Wenn genau eine Kombination gezogen wird und alle gleich wahrscheinlich sind, beträgt die Chance auf genau diese Kombination 1 zu 13.983.816. Zusatzzahlen, Gewinnklassen und mehrere Tipps verändern die vollständige Gewinnwahrscheinlichkeit.

Die Rechnung setzt eine faire Ziehung ohne Wiederholung voraus. Werden Zahlen zurückgelegt, zählt ein anderes Modell. Auch die Reihenfolge kann in manchen Spielen relevant sein. Lesen Sie die konkrete Spielregel, bevor Sie n und k übertragen.

Ein häufiger Irrtum ist, „seltene“ oder lange nicht gezogene Zahlen für wahrscheinlicher zu halten. Bei unabhängigen fairen Ziehungen hat jede zulässige Kombination im nächsten Versuch dieselbe Chance. Der Binomialkoeffizient bewertet keine Zahlenauswahl als günstiger.

Rekursive Berechnung und dynamische Tabelle

Die Pascal-Rekursion kann eine ganze Tabelle aufbauen: Man beginnt an den Rändern mit 1 und addiert jeweils zwei Nachbarn. Das ist anschaulich und liefert viele C(n,k)-Werte gleichzeitig. Für nur einen einzelnen Koeffizienten benötigt sie jedoch mehr Speicher als die Produktform.

Eine naive rekursive Funktion, die C(n−1,k−1) und C(n−1,k) immer neu berechnet, wiederholt dieselben Teilprobleme exponentiell oft. Memoisierung oder dynamische Programmierung speichert bereits ermittelte Werte. Die hier verwendete multiplikative Schleife braucht nur einen laufenden Zahlenwert.

Für modulare Aufgaben, etwa C(n,k) modulo einer Primzahl, gelten weitere Zahlentheorieverfahren. Das vollständige riesige Ergebnis muss dann nicht unbedingt gebildet werden. Dieser Rechner gibt dagegen den exakten sicheren Ganzzahlwert bis n = 52 aus.

Erwartungswert nicht mit Einzelwahrscheinlichkeit verwechseln

Für eine Binomialverteilung ist der Erwartungswert E(X) = np und die Varianz np(1−p). Bei n = 20 und p = 0,5 werden im Mittel zehn Erfolge erwartet. Das bedeutet nicht, dass zehn Erfolge in jeder Serie auftreten oder dass P(X=10) gleich 50 Prozent ist.

Die Ausgabe P(X=k) betrifft genau einen Wert k. Fragen wie „höchstens sechs“ oder „mindestens sechs“ benötigen Summen mehrerer Binomialwahrscheinlichkeiten. Für höchstens sechs addiert man P(X=0) bis P(X=6). Diese kumulative Rechnung ist nicht in der Ergebnisbox enthalten.

Bei statistischen Tests kommen zusätzlich Hypothese, Signifikanzniveau und ein- oder zweiseitige Fragestellung hinzu. Ein einzelner Koeffizient entscheidet keine wissenschaftliche Schlussfolgerung.

Häufige Fragen zum Binomialkoeffizienten

References

• Wolfram MathWorld – Binomial Coefficient
• Wolfram MathWorld – Pascal’s Triangle
• NIST/SEMATECH – Binomial Distribution