Binomialkoeffizient

In der Mathematik sind Binomialkoeffizienten bestimmte reelle Zahlen, die in vielen Bereichen auftreten, z.B. in der Kombinatorik und der Analysis.

Ein Binomialkoeffizient hängt von 2 Zahlen ab; wenn diese n und k sind, dann schreibt man den Binomialkoeffizienten "n über k" als

{n \choose k}

Definition

Die einfachste Definition gilt für den Fall, dass n und k ganze Zahlen sind, wobei n ≥ 0 ist. In diesem Fall definiert man

{n \choose k}={\begin{cases}{\frac {n!}{k!(n-k)!}}&{\mbox{wenn }}n\geq k\geq 0\\0&{\mbox{wenn }}\;k>n\;{\mbox{oder }}k<0\end{cases}}

Dabei ist n! die Fakultät von n, n! = n·(n-1)·...·2·1.

Es ist

{\frac {n!}{k!\,(n-k)!}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{1\cdot 2\cdot 3\cdots k}}.

Berechnung, Algorithmus

Für die Implementierung auf einem Rechner empfiehlt sich z.B. bei der Berechnung von

{49 \choose 6}={\frac {49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}}

die Reihenfolge

(((((49\cdot 48)/2\cdot 47)/3\cdot 46)/4\cdot 45)/5\cdot 44)/6;

alle auftretenden Divisionen gehen ohne Rest auf. Dabei entstehen nicht so große Zahlen, als wenn man die beiden Produkte am Ende dividiert hätte:

{\frac {49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}}={\frac {10068347520}{720}}

Mithilfe der Beziehung

{n \choose k}={n \choose n-k}

kann man die Berechnung verkürzen, falls $k>n/2$ ist.

Das folgende Codefragment zeigt die Berechnung:

   If k + k > n Then k = n - k
   BinomialKoeffizient = 0
   If k >= 0 Then
       BinomialKoeffizient = 1
       For i = 1 To k
           BinomialKoeffizient = BinomialKoeffizient * (n-i+1) / i
       Next i
   End If

Beispiele

{5 \choose 3}={\frac {5!}{3!\cdot 2!}}={\frac {5\cdot 4\cdot 3!}{2!\cdot 3!}}={\frac {5\cdot 4}{2!}}={\frac {20}{2}}=10

{3 \choose 5}=0

,

{n \choose 1}=n

,

{n \choose n}=1

Kombinatorische Deutung

Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine wichtige Rolle: $p \choose q$ ist die Anzahl der Möglichkeiten, aus einer Menge mit p Elementen q Elemente auszuwählen, ohne auf die Reihenfolge bei der Auswahl zu achten.

Damit lässt sich z.B. die Anzahl der möglichen Ziehungen beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) berechnen:

{49 \choose 6}=13.983.816

Der Kehrwert 1:13.983.816 entspricht dann der Wahrscheinlichkeit, mit einem Tipp 6 Richtige zu erzielen. Die Wahrscheinlichkeit für 5 Richtige bei 6 aus 49 lässt sich aber nicht über einen einzelnen Binomialkoeffizienten berechnen. Es wird die Hypergeometrische Verteilung benötigt, in deren Berechnung dann mehrere Binomialkoeffizienten ausgewertet werden müssen.

Rekursive Darstellung und Pascalsches Dreieck

Für den Binomialkoeffizienten nichtnegativer ganzer Zahlen n und k hat man folgende rekursive Darstellung:

{0 \choose 0}=1;\quad {n \choose n}={n \choose 0}=1;\quad {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

Diese Formel eignet sich zum Beispiel, um alle Binomialkoeffizienten bis zu einer vorgegebenen Schranke für $n$ zu bestimmen, ein Schema dazu ist das Pascalsche Dreieck: dort entspricht sie der Tatsache, dass jede Zahl die Summe der beiden über ihr stehenden ist.

Beweis: Es sei $X$ eine $n$ -elementige Menge und $x\in X$ ein festes Element. Dann zerfallen die $k$ -elementigen Teilmengen von $X$ in zwei Klassen:

die Teilmengen, die $x$ enthalten; sie bestehen also aus $x$ zusammen mit einer $(k-1)$ -elementigen Teilmenge der $(n-1)$ -elementigen Menge $X\setminus \{x\}$
die Teilmengen, die $x$ nicht enthalten; sie sind $k$ -elementige Teilmengen der $(n-1)$ -elementigen Menge $X\setminus \{x\}$ .

Relationen zwischen Binomialkoeffizienten

{n \choose k}={n \choose n-k};\quad {n+1 \choose k+1}={n \choose k}+{n \choose k+1}

{n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=\sum _{k=0}^{n}{n \choose k}=2^{n}

{n \choose 0}-{n \choose 1}+{n \choose 2}-\cdots =\sum _{k=0}^{n}(-1)^{k}\cdot {n \choose k}=0

{n \choose n}+{n+1 \choose n}+\cdots +{n+m \choose n}=\sum _{k=0}^{m}{n+k \choose n}={n+m+1 \choose n+1}

k\cdot {n \choose k}=n\cdot {n-1 \choose k-1}

{m+n \choose k}=\sum _{j=0}^{k}{m \choose j}{n \choose k-j}

Die letzte Gleichung ist bekannt als Vandermondesche Identität.

Verallgemeinerung

Eine Verallgemeinerung, die in der Analysis eine Rolle spielt, erhält man, wenn man statt n eine beliebige reelle oder komplexe Zahl α zulässt und k weiterhin eine ganze Zahl ist. In diesem Fall ist

{\alpha  \choose k}={\begin{cases}{\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k!}}&{\mbox{wenn }}k\geq 0\\0&{\mbox{wenn }}k<0\end{cases}}

der Binomialkoeffizient "α über k" (das leere Produkt im Fall k=0 ist definiert als 1). Diese Definition stimmt für nichtnegative ganzzahlige α mit der ersten überein.

Für reelle α erlaubt die Betafunktion $\beta (x,y)$ eine Erweiterung der Definition auf reelle k, aber nur für k>-1 und α-k>-1:

{\alpha  \choose k}={\frac {1}{(\alpha +1)\cdot \beta (k+1,\alpha -k+1)}}

Beispielsweise ist

{2{,}5 \choose 2}={\frac {2{,}5\cdot 1{,}5}{2!}}={\frac {3{,}75}{2}}=1{,}875

und

{-1 \choose k}={\frac {(-1)\cdot (-2)\cdots (-k)}{k!}}=(-1)^{k}.

Binomische Reihe

Der Name "Binomialkoeffizient" ist abgeleitet vom Auftreten in der binomischen Reihe

(1+x)^{\alpha }=\sum _{k=0}^{\infty }{\alpha  \choose k}x^{k}

Ist α ganzzahlig, so bricht die Reihe nach dem Glied k = α ab, d.h. alle weiteren Glieder sind 0. Für nicht ganzzahliges α liefert die binomische Reihe die Taylorreihe von $(1+x)^{\alpha }$ mit Entwicklungspunkt 0.