Hauptmenü öffnen

Der Binomialkoeffizient ist eine mathematische Funktion, mit der sich eine der Grundaufgaben der Kombinatorik lösen lässt. Er gibt an, auf wie viele verschiedene Arten man Objekte aus einer Menge von verschiedenen Objekten auswählen kann (ohne Zurücklegen, ohne Beachtung der Reihenfolge). Der Binomialkoeffizient ist also die Anzahl der -elementigen Teilmengen einer -elementigen Menge.

„49 über 6“ (bzw. „45 über 6“ in Österreich und der Schweiz) ist z. B. die Anzahl der möglichen Ziehungen beim Lotto (ohne Berücksichtigung der Zusatzzahl).

Ein Binomialkoeffizient hängt von zwei natürlichen 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.

Den Namen erhielten diese Zahlen, da sie als Koeffizienten in den Potenzen des Binoms auftreten; es gilt der sogenannte binomische Lehrsatz:

Eine Erweiterung des aus der Kombinatorik stammenden Binomialkoeffizienten stellt der allgemeine Binomialkoeffizient dar, der in der Analysis verwendet wird.

Inhaltsverzeichnis

DefinitionBearbeiten

Für eine komplexe Zahl   und eine nichtnegative ganze Zahl   ist der Binomialkoeffizient „n über k“ auf folgende Weise definiert:

 

wobei   die Fakultät von   bezeichnet. Das leere Produkt ( ) ist dabei  .

Handelt es sich bei   um eine nichtnegative ganze Zahl mit  , so kann man die aus der Kombinatorik bekannte Definition verwenden:

 

EigenschaftenBearbeiten

Wird außer   auch   auf nichtnegative ganze Zahlen eingeschränkt, so gilt:

  •   ist stets eine nichtnegative ganze Zahl. Ist  , so ist  , anderenfalls ist  .
  •  
  •  
  •  
  •  
  •  . Für   ist der rechte Summand  .

Im allgemeinen Fall reeller oder komplexer Werte für   können einige der hier angeführten Ausdrücke undefiniert im oben angegebenen Sinn werden, falls nämlich   nicht mehr ganz und nichtnegativ sein sollte; das betrifft die Aussagen  ,   und  . Es zeigt sich jedoch, dass diese Aussagen korrekt werden, wenn man entsprechend der untenstehenden analytischen Verallgemeinerung über die Betafunktion auch für   komplexe Werte zulässt.

Symmetrie der BinomialkoeffizientenBearbeiten

Ganzzahlige Binomialkoeffizienten sind symmetrisch im Sinne von

 

für alle nichtnegativen   und  .

Beweis
 
Beispiel
 
 
 

Rekursive Darstellung und Pascalsches DreieckBearbeiten

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!):

Das gleiche Dreieck dargestellt in den  -Binomialsymbolen:

 
 
 
 
 
 
 
 

Algorithmus zur effizienten BerechnungBearbeiten

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 k == 0 dann rückgabe 1
2  wenn 2*k > n dann k = n-k
3  ergebnis = 1
4  für i = 1 bis k
5      ergebnis = ergebnis * (n - k + i) / i
6  rückgabe ergebnis

Diese Rechenmethode nutzen auch Taschenrechner, wenn sie die Funktion anbieten. Sonst wäre die Rechenkapazität für   erschöpft. 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 KombinatorikBearbeiten

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 MengenBearbeiten

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 1Bearbeiten

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 2Bearbeiten

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  .

BeispielBearbeiten

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 sehr einfach 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 derart kombiniert.

Weitere Beispiele siehe unter: Kombination (Kombinatorik) → Beispiele

Kombinatorische BeweiseBearbeiten

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  .

KombinationsmengenBearbeiten

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 BinomialkoeffizientenBearbeiten

Summen mit BinomialkoeffizientenBearbeiten

 

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 BinomialkoeffizientenBearbeiten

  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.

Summe verschobener BinomialkoeffizientenBearbeiten

 

und ebenso

 

Vandermondesche IdentitätBearbeiten

 

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:

 

DivisionsresteBearbeiten

Ist   eine Primzahl,   und  , dann ist

 

Das heißt, modulo   kann   mit Hilfe der Darstellungen von   und   zur Basis   effizient berechnet werden, nämlich „ziffernweise“.

Binomialkoeffizienten in der AnalysisBearbeiten

VerallgemeinerungBearbeiten

Eine Verallgemeinerung, die in der Analysis eine Rolle spielt, erhält man, wenn man für   eine beliebige komplexe Zahl   zulässt, aber   weiterhin als ganzzahlig voraussetzt. In diesem Fall ist

 

der Binomialkoeffizient „  über  “ (das leere Produkt im Fall   ist definiert als 1). Diese Definition stimmt für nichtnegative ganzzahlige   mit der kombinatorischen Definition (also der Definition von   als die Anzahl aller  -elementigen Teilmengen einer festen  -elementigen Menge) überein, und für nichtnegative   mit der algebraischen Definition (also der Definition von   als das Produkt  ).

Beispielsweise ist

 

und

 

Auch der zweite Parameter   lässt sich auf beliebige komplexe Belegung   verallgemeinern, wenn mit Hilfe der Betafunktion   für   definiert wird:

 

wobei   die Gammafunktion bezeichnet. Ist dabei   oder   eine negative ganze Zahl, so ist der Wert der rechten Seite 0, weil die nichtpositiven ganzen Zahlen die (einzigen) Polstellen von   sind.

Ersichtlich gilt weiterhin die Symmetriebeziehung

 ,

insbesondere

 ,
 

und bei nichtnegativem ganzen  

 .

Um das Vorzeichen aus dem ersten Parameter zu extrahieren, sofern er ganzzahlig ist, lässt sich die Relation

 

angeben.

Allgemein gilt für komplexe  ,   die Beziehung

 .

Eine weitere Verallgemeinerung bieten die Multinomialkoeffizienten, die bei der Verallgemeinerung des binomischen auf den multinomialen Lehrsatz benötigt werden.

Binomische ReihenBearbeiten

Für   und   mit   erhält man die Beziehung

 

die eine Verallgemeinerung der geometrischen Reihe darstellt und zu den binomischen Reihen gehört.

Ist  ,   sowie  , konvergiert die folgende Reihe gemäß

 

Exaktere Bedingungen für   und   sind im Artikel Binomische Reihe angegeben.

Summenausdruck für die BetafunktionBearbeiten

Eine weitere Beziehung kann man für alle   relativ einfach mit vollständiger Induktion beweisen,

 

woraus unmittelbar die Symmetrie

 

folgt. Eine Verallgemeinerung für   mit   und   lautet

 

Gaußsche Produktdarstellung für die GammafunktionBearbeiten

Mit der letzten Formel aus dem vorherigen Abschnitt ist für  

 

Betrachtet man den Fall  , ersetzt die Brüche in der Summe durch Integrale gemäß

 

und fasst die Summe der Potenzen den binomischen Formeln entsprechend zusammen, erhält man

 

wobei beim letzten Integral die Substitution   angewendet wurde. Schließlich hat man die Gleichung

 

woraus sich durch den Grenzübergang   direkt die Gaußsche Produktdarstellung der Gammafunktion,

 

ergibt.[1]

Digammafunktion und Euler-Mascheroni-KonstanteBearbeiten

Für   mit   gilt

 

was sich ebenfalls über Induktion nach   beweisen lässt. Für den Spezialfall   vereinfacht sich diese Gleichung zu

 

wobei   die Folge der Harmonischen Zahlen, also der Partialsummen der Harmonischen Reihe ist. Die Umwandlung der linken Summe in eine Reihe (Limit   statt  ) ist dabei erlaubt wegen   für  

  ist andererseits darstellbar als

 

mit der Digammafunktion   und der Euler-Mascheroni-Konstanten  

  kann auf komplexe Werte   - außer auf negative ganze Zahlen - fortgesetzt werden. Man bekommt so die Reihe

 

als komplexe Interpolation der Folge der Harmonischen Zahlen.

TriviaBearbeiten

Die wörtliche Übersetzung von „  über  “ ins Englische „  over  “ bezeichnet nicht den Binomialkoeffizienten  , sondern den Bruch  . Korrekt ist „  choose  “.

WeblinksBearbeiten

  Wiktionary: Binomialkoeffizient – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
  Commons: Binomialkoeffizient – Sammlung von Bildern, Videos und Audiodateien

EinzelnachweiseBearbeiten

  1. Disquisitiones generales circa seriem infinitam 1+… 1813, S. 26 (auch in Carl Friedrich Gauß: Werke. Band 3, S. 145).