Der Binomialkoeffizient ist eine mathematische Funktion, mit der sich eine der Grundaufgaben der Kombinatorik lösen lässt, nämlich auf wie viele verschiedene Arten man aus einer Menge von verschiedenen Objekten jeweils Objekte auswählen kann (ohne Zurücklegen und ohne Beachtung der Reihenfolge). Der Binomialkoeffizient ist also die Anzahl der -elementigen Teilmengen in der Potenzmenge einer -elementigen Grundmenge.
Eine Erweiterung des aus der Kombinatorik stammenden Binomialkoeffizienten stellt der allgemeine Binomialkoeffizient dar, der in der Analysis verwendet wird.
Ein bekanntes Beispiel für die Anwendung von Binomialkoeffizienten sind die Anzahl der möglichen Ziehungen beim Lotto wie z. B. „49 über 6“ in Deutschland, „45 über 6“ in Österreich, „42 über 6“ der Schweiz (jeweils ohne Berücksichtigung der Zusatzzahl) oder „50 über 5“ und bei Zusatzzahl „12 über 2“ bei Euromillions und Eurojackpot.
Darstellung Ein Binomialkoeffizient hängt von zwei nichtnegativen ganzen Zahlen und ab. Er wird mit dem Symbol
geschrieben und als „n über k“, „k aus n“ oder „n tief k“ gesprochen. Die englische Abkürzung nCr für n choose r findet sich als Beschriftung auf Taschenrechnern.
Bezeichnung Den Namen erhielten diese Zahlen, da sie als Koeffizienten in den Potenzen des Binoms auftreten; es gilt der sogenannte binomische Lehrsatz:
Definition
Für ganze Zahlen ist der Binomialkoeffizient „n über k“ auf folgende Weise definiert: , wobei die Fakultät von bezeichnet. Für setzt man zudem .
Grundlegende Rechenregeln
Durch Wegkürzen der Fakultäten können Binomialkoeffizienten auch mit großen Werten in annehmbarer Zeit berechnet werden. Bei kann durch oder bei durch gekürzt werden.
Unmittelbar aus der Definition ergeben sich für die Umformungen:
Es gilt weiter:
ist stets eine nichtnegative ganze Zahl. Ist , so ist , anderenfalls ist .
Für ist der rechte Summand .
Symmetrie
Ganzzahlige Binomialkoeffizienten sind symmetrisch im Sinne von
für alle nichtnegativen und .
Beweis
Beispiel
Rekursive Darstellung und Pascalsches Dreieck
Für ganze Zahlen und mit lassen sich die Binomialkoeffizienten auch durch folgende Rekursionsvorschrift ermitteln: für alle für alle und für alle mit
Mit ihrer Hilfe lassen sich leicht alle Binomialkoeffizienten bis zu einer vorgegebenen Schranke für bestimmen, ein Schema dafür ist das Pascalsche Dreieck: Der rekursive Teil entspricht dort der Tatsache, dass jede Zahl die Summe der beiden über ihr stehenden Zahlen ist.
Beweis
Den Koeffizienten findet man dabei in der -ten Zeile an der -ten Stelle (beide ab Null gezählt!):
zentriert|Pascalsches Dreieck (bis zur 8. Zeile)
Das gleiche Dreieck dargestellt in den -Binomialsymbolen:
Algorithmus zur effizienten Berechnung
Für ganzzahlige existiert ein effizienter Algorithmus, der die Produktformel
des Binomialkoeffizienten anwendet. Auf Grund des stetigen Wechsels zwischen Multiplikation und Division wachsen die Zwischenergebnisse nicht unnötig an. Zusätzlich sind auch alle Zwischenergebnisse natürliche Zahlen.
Um unnötigen Rechenaufwand zu vermeiden, berechnet man im Fall den Binomialkoeffizienten:
Der folgende Pseudocode verdeutlicht die Berechnung: binomialkoeffizient(n, k) 1 wenn 2*k > n dann k = n-k 2 ergebnis = 1 3 für i = 1 bis k 4 ergebnis = ergebnis * (n + 1 - i) / i 5 rückgabe ergebnis
Diese Rechenmethode nutzen auch Taschenrechner, wenn sie die Funktion anbieten. Sonst wäre die Rechenkapazität oftmals für erschöpft, da . Die Beschriftung der Funktionstaste mit nCr beschreibt die Reihenfolge der Eingabewerte in Infixnotation; zunächst Anzahl der Elemente n, dann die Funktionstaste Combinations, dann Anzahl der gewählten Objekte r (im Artikel mit k bezeichnet).
Die Berechnung nPr (engl. Permutations) berücksichtigt die Permutationen der r Elemente, die Division durch unterbleibt: .
Der Binomialkoeffizient in der Kombinatorik
In der abzählenden Kombinatorik gibt
die Anzahl der Kombinationen ohne Wiederholung von Elementen aus Elementen an. Durch diese Eigenschaft spielt der Binomialkoeffizient eine zentrale Rolle in der Kombinatorik und findet Eingang in die Berechnung und in die Formeln anderer kombinatorischer Größen.
Veranschaulichung mit Mengen
Vergleiche auch: Kombination (Kombinatorik) → Mengendarstellung
Eine andere Interpretation von Kombinationen ohne Wiederholung von k aus n Elementen ist die Anzahl aller -elementigen Teilmengen einer -elementigen Menge.
Sie kann anschaulich etwa so gedeutet werden:
Variante 1
Zunächst zählt man alle -Tupel mit paarweise verschiedenen Elementen, die sich aus der -elementigen Ausgangsmenge zusammenstellen lassen. Es gibt Möglichkeiten der Wahl des ersten Tupel-Elements. Nach jeder beliebigen Wahl dieses ersten gibt es nur noch Wahlmöglichkeiten für das zweite Element, nach dessen Wahl nur noch für das dritte usw., bis hin zu Wahlmöglichkeiten für das -te und letzte Tupel-Element. Die Anzahl aller so zusammengestellten -Tupel ist also das Produkt von Faktoren, das sich mit Hilfe der Fakultät auch als notieren lässt. Nun sind aber genau je der gezählten -Tupel Permutationen voneinander und entsprechen daher ein und derselben -elementigen Teilmenge. Nach Division durch diese „Zähl-Vielfachheit“ ergibt sich also tatsächlich als die gesuchte Teilmengenanzahl.
Variante 2
Eine andere, symmetrischere Veranschaulichung betont nicht den Akt der Auswahl von aus Elementen, sondern den Aspekt der Zerlegung in zwei Teilmengen aus und Elementen. Angenommen, ein -elementiges Ausgangstupel bestehe aus roten und weißen irgendwie aufgereihten Elementen. Bildet man alle Permutationen dieser Aufreihung, so sind je davon farblich ununterscheidbar, denn je Permutationen der roten Elemente untereinander ändern nichts an der Farbsequenz, ebenso wenig wie je davon unabhängige Permutationen innerhalb der weißen. Es gibt also nur farblich verschiedene Sequenzen der Länge mit allen möglichen unterschiedlichen Belegungen durch je rote Elemente. Jede Sequenz lässt sich nun aber eineindeutig einer der -elementigen Teilmengen einer -elementigen Menge zuordnen. Dasselbe gilt wegen der Symmetrie von rot und weiß oder von und auch für die komplementären -elementigen Teilmengen. Die Gesamtzahl dieser Teilmengen ist damit je .
Erstes Beispiel
Für die Anzahl der möglichen Ziehungen oder Tippscheine beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) gilt:
Es gibt hier offensichtlich genau eine Möglichkeit, 6 Richtige zu tippen. zählt die Möglichkeiten für 0 Richtige, nämlich alle 6 Tipps aus den 43 Falschen zu wählen. Die Anzahl verschiedener Tipps mit 5 Richtigen ergibt sich zu , denn es gibt 6 Möglichkeiten, nur 5 der 6 gezogenen Zahlen zu tippen (oder eine davon auszulassen), und dann jeweils Möglichkeiten, den ausgelassenen Tipp auf eine der 43 falschen Zahlen zu setzen. Allgemein ergibt sich die Anzahl der verschiedenen Tipps mit Richtigen bei 6 aus 49 mit derselben Überlegung zu . Bei 6, 0 und 5 Richtigen fällt kaum auf, dass die verwendeten Faktoren , und eigentlich einfache Binomialkoeffizienten sind. Die Summe aller genannten Tippzahlen ergibt die Gesamtzahl 13983816 aller möglichen Tipps – das folgt aus der unten angegebenen Vandermondeschen Identität.
Die Wahrscheinlichkeit für 6 mit einem Tipp erzielte Richtige ist also , die für 5 Richtige ist . Für 0 Richtige ergeben sich mit schon etwa 44 %. Die allgemeine Wahrscheinlichkeit für Richtige ist ein Spezialfall der hypergeometrischen Verteilung, die gerade drei Binomialkoeffizienten derartig kombiniert.
Zweites Beispiel
Ein weiteres Beispiel behandelt einen Sack voller farbiger Murmeln. Die Wahrscheinlichkeit, dass aus insgesamt roten, grünen und blauen Murmeln genau rote, grüne und blaue Murmeln gezogen werden, wobei insgesamt Murmeln herauszunehmen sind, hat folgenden Wert:
Wenn beispielsweise aus einem Murmelsack mit insgesamt roten, grünen und blauen Murmeln genau sechs Murmeln blind herausgenommen werden sollen, dann beträgt die Wahrscheinlichkeit, dass sich unter den sechs herausgenommenen Murmeln genau rote, grüne und blaue Murmeln befinden, exakt :
Weitere Beispiele siehe unter: Kombination (Kombinatorik) → Beispiele
Kombinatorische Beweise
Die kombinatorische Deutung erlaubt auch einfache Beweise von Relationen zwischen Binomialkoeffizienten, etwa durch doppeltes Abzählen. Beispiel: Für gilt:
Beweis: Es sei eine -elementige Menge und ein festes Element. Dann zerfallen die -elementigen Teilmengen von in zwei Klassen: die Teilmengen, die enthalten; sie bestehen also aus zusammen mit einer -elementigen Teilmenge der -elementigen Menge , die Teilmengen, die nicht enthalten; sie sind -elementige Teilmengen der -elementigen Menge .
Kombinationsmengen
Die Menge aller -elementigen Teilmengen einer Menge wird wegen ihrer Mächtigkeit gelegentlich auch mit bezeichnet. Damit gilt für jede endliche Menge :
Ausdrücke mit Binomialkoeffizienten
Summen mit Binomialkoeffizienten
Dieser Formel liegt ein kombinatorischer Sachverhalt zu Grunde. Da die Anzahl aller -elementigen Teilmengen einer -elementigen Menge ist, ergibt sich durch die Summation die Anzahl aller ihrer Teilmengen, also . Die Formel lässt sich auch aus dem binomischen Lehrsatz herleiten, indem man setzt.
Summen mit alternierenden Binomialkoeffizienten
für . Diese Formel folgt für ungerade aus der Symmetrie des Binomialkoeffizienten. Für beliebige lässt sie sich aus dem binomischen Lehrsatz herleiten, indem und (oder und ) gesetzt wird. Summen von Binomialkoeffizienten mit geraden bzw. ungeraden Anzahlen ausgewählter Objekte
Durch Subtraktion bzw. Addition obiger Gleichungen und und anschließende Halbierung ist für zu erhalten:
wie auch .
Hierbei sind Gaußklammern.
Summe verschobener Binomialkoeffizienten
Ausgehend vom Induktionsanfang für beliebiges , der die Rekursionsvorschrift für Binomialkoeffizienten nutzt, ist mit Induktion nach unter erneuter Nutzung der Rekursionsvorschrift leicht zu beweisen:
Wegen Symmetrie der Summanden wie auch der Summe gilt ebenso: .
Vandermondesche Identität
Für nicht-negative ganze Zahlen gilt: Formel (5).
Es gibt auch hier ein kombinatorisches Argument: Die rechte Seite entspricht der Anzahl von -elementigen Teilmengen einer -elementigen Menge von Kugeln. Man kann sich nun vorstellen, dass die Kugeln zwei verschiedene Farben haben: Kugeln seien rot und Kugeln grün. Eine -elementige Teilmenge besteht dann aus einer gewissen Anzahl von roten Kugeln und vielen grünen. Für jedes mögliche gibt der entsprechende Summand auf der linken Seite die Anzahl der Möglichkeiten für solch eine Aufteilung in rote und grüne Kugeln an. Die Summe liefert die Gesamtzahl. Ein oft als einfacher empfundener Beweis verwendet den Binomischen Lehrsatz in der Form
sowie den Ansatz
und Koeffizientenvergleich.
Im Spezialfall ergibt sich aus der Vandermondeschen Identität folgende Formel für die Quadratsummen:
Mit dem Kürzel wird der Mittlere Binomialkoeffizient (Zentralbinomialkoeffizient, Central Binomial Coefficient) gekennzeichnet.rechts|200x200px|Darstellung der Hockey-Stick-Identität im Pascalschen Dreieck.
Hockey-Stick-Identität
Für mit gilt:
Der Name Hockey-Stick-Identität (Hockeyschläger-Identität) rührt von der graphischen Darstellung der Identität auf dem Pascalschen Dreieck her: Wenn die einzelnen Summanden und der Wert der Summe selbst farblich hervorgehoben werden, erinnert die Form an einen Hockeyschläger.
Fibonacci-Zahlen
Die Fibonacci-Zahlenfolge ist eine unendliche Folge aus natürlichen Zahlen, welche zweimal mit der Zahl Eins beginnt und bei der jede Zahl als Summe der beiden in der Folge vorangehenden Zahlen entsteht. Es gilt also , und für stets .
Mit den Binomialkoeffizienten können die Fibonaccizahlen in Form einer geschlossenen Summe dargestellt werden:
Beispielsweise gilt für diese Fibonacci-Zahlen aus den ungeraden Indizes:
Und es gilt für jene Fibonacci-Zahlen aus den geraden Indizes: