Binomialkoeffizient

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 k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann (ohne Zurücklegen, ohne Beachtung der Reihenfolge). Der Binomialkoeffizient ist also die Anzahl der k-elementigen Teilmengen einer n-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 Zahlen n und k ab. Er wird mit dem Symbol

$\binom nk$

geschrieben und als „n über k“, „k aus n“ oder „n tief k“ gesprochen. Die englische Abkürzung nCr für from n choose r findet sich als Beschriftung auf Taschenrechnern.

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

$\begin{align} (x+y)^n &= \binom n0 x^n + \binom n1 x^{n-1} y + \dotsb + \binom n{n-1} x y^{n-1} + \binom nn y^n\\ &= \sum_{k=0}^n \binom n k x^{n-k} y^k \end{align}$

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

Definition

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

$\begin{align} \binom nk &= \frac n1 \cdot \frac{n-1}2 \dotsm \frac{n-(k-1)}k\\ &= \frac{n\cdot(n-1) \dotsm (n-k+1)}{k!}\\ &= \prod_{j=1}^k \frac{n + 1 - j}j, \end{align}$

wobei k! die Fakultät von k bezeichnet. Das leere Produkt (k = 0) ist dabei 1.

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

$\binom nk = \frac{n!}{k! \cdot (n-k)!}.$

Eigenschaften

Für nichtnegative ganze Zahlen n und k ist $\tbinom nk$ stets eine nichtnegative ganze Zahl. Ist dabei k > n, so gilt

$\binom nk=0.$

Rechenregeln

$\binom n0 = \binom nn = 1$

$\binom n1 = \binom n{n-1} = n$

$k \cdot \binom nk = n \cdot \binom{n-1}{k-1}$

$\binom{n+1}{k+1} = \binom nk + \binom n{k+1}$

(sämtliche Regeln gelten auch für die Verallgemeinerung mit reellen oder komplexen Werten für n)

Symmetrie der Binomialkoeffizienten

Ganzzahlige Binomialkoeffizienten sind symmetrisch im Sinne von

$\binom nk = \binom n{n-k}$

für alle nichtnegativen n und k.

Beweis

$\begin{align} \binom n{n-k} &= \frac{n!}{(n-k)! \cdot (n-(n-k))!}\\ &= \frac{n!}{(n-k)! \cdot k!}\\ &= \frac{n!}{k! \cdot (n-k)!}\\ &= \binom nk \end{align}$

Beispiel

$\binom 5 3 = \binom 5 {5-3} = \binom 5 2$

$\binom 5 3 = \frac{5!}{3! \cdot (5-3)!} = \frac{5!}{3! \cdot 2!} = \frac{1\cdot 2\cdot 3\cdot 4\cdot 5}{(1\cdot 2\cdot 3) \cdot (1\cdot 2)} = \frac{4\cdot 5}{1\cdot 2} = 10$

$\binom 5 2 = \frac{5!}{2! \cdot (5-2)!} = \frac{5!}{2! \cdot 3!} = \frac{4\cdot 5}{1\cdot 2} = 10$

Rekursive Darstellung und Pascalsches Dreieck

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

$\binom{n}{n} = \binom{n}{0} = 1;\quad \binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}.$

Diese Formel eignet sich auch, um alle Binomialkoeffizienten bis zu einer vorgegebenen Schranke für n zu bestimmen, ein Schema dazu ist das Pascalsche Dreieck: Dort entspricht sie der Konstruktionsvorschrift, dass jede Zahl die Summe der beiden über ihr stehenden Zahlen ist (in der Formel oben k durch k − 1 ersetzen):

$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$

oder andersherum (n durch n − 1 ersetzen):

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$

Beweis:

$\begin{align} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!} {(k-1)!\cdot(n-k)!} +\frac{(n-1)!} {k!\cdot(n-k-1)!}\\[.5em] &= \frac{(n-1)! \cdot k}{k\cdot(k-1)! \cdot (n-k)!} + \frac{(n-1)!\cdot (n-k)} {k! \cdot (n-k) \cdot (n-k-1)!}\\[.5em] &= \frac{(n-1)! \cdot (k+n-k)} {k! \cdot (n-k)!}\\[.5em] &= \frac{n!} {k! \cdot (n-k)!} = \binom{n}{k}. \end{align}$

Den Koeffizienten $\tbinom{n}{k}$ findet man dabei in der (n + 1)-ten Zeile, an der (k + 1)-ten Stelle (da es keine »nullte Zeile/Stelle« gibt):

Das gleiche Dreieck dargestellt in den $\tbinom{n}{k}-$Binomialsymbolen:

$\tbinom{0}{0}$
$\tbinom{1}{0}\quad\tbinom{1}{1}$
$\tbinom{2}{0}\quad\tbinom{2}{1}\quad\tbinom{2}{2}$
$\tbinom{3}{0}\quad\tbinom{3}{1}\quad\tbinom{3}{2}\quad\tbinom{3}{3}$
$\tbinom{4}{0}\quad\tbinom{4}{1}\quad\tbinom{4}{2}\quad\tbinom{4}{3}\quad\tbinom{4}{4}$
$\tbinom{5}{0}\quad\tbinom{5}{1}\quad\tbinom{5}{2}\quad\tbinom{5}{3}\quad\tbinom{5}{4}\quad\tbinom{5}{5}$
$\tbinom{6}{0}\quad\tbinom{6}{1}\quad\tbinom{6}{2}\quad\tbinom{6}{3}\quad\tbinom{6}{4}\quad\tbinom{6}{5}\quad\tbinom{6}{6}$
$\tbinom{7}{0}\quad\tbinom{7}{1}\quad\tbinom{7}{2}\quad\tbinom{7}{3}\quad\tbinom{7}{4}\quad\tbinom{7}{5}\quad\tbinom{7}{6}\quad\tbinom{7}{7}$

Algorithmus zur effizienten Berechnung

Für ganzzahlige n existiert ein effizienter Algorithmus, der die Produktformel

${n \choose k} = \prod_{i=1}^k \frac{n-k+i}{i}$

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 k > n / 2 den Binomialkoeffizienten:

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

Der folgende Pseudocode verdeutlicht die Berechnung:

binomialkoeffizient(n, k)
1  wenn k = 0 dann rückgabe 1
2  wenn 2k > n
3      dann führe aus ergebnis $\leftarrow$ binomialkoeffizient(n, n-k)
4  sonst führe aus ergebnis $\leftarrow$ n-k+1
5          von i $\leftarrow$ 2 bis k
6              führe aus ergebnis $\leftarrow$ ergebnis $\cdot$ (n - k + i)
7                        ergebnis $\leftarrow$ ergebnis : i
8  rückgabe ergebnis

Die Rechenmethode nutzen auch Taschenrechner, wenn sie die Funktion anbieten. Sonst wäre die Rechenkapazität für n=69 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 abgekürzt).

Die Berechnung nPr (engl. Permutations) berücksichtigt die Permutationen der r Elemente, die Division durch r! unterbleibt:

P(n,r) = n! / (n - r)!.

Der Binomialkoeffizient in der Kombinatorik

Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine zentrale Rolle, denn $\tbinom n k$ ist die Anzahl der Möglichkeiten, aus einer Menge mit n Elementen k Elemente auszuwählen, wobei die Reihenfolge der ausgewählten Elemente nicht berücksichtigt wird.

Anschaulich lässt sich das so erklären: Man berechne mit n! alle möglichen Vertauschungen, suche sich k „Felder“ aus (beispielsweise 6 beim Lotto) und frage sich, wie viele Möglichkeiten es gibt, diese Felder zu besetzen. Da es keine Rolle spielt, welches „Ereignis“ sich auf welchem Feld ereignet hat, dividiert man alle unter diesen k Elementen möglichen Vertauschungen mit k! heraus. Da es auch keine Rolle spielt, wie die Anordnung auf den uninteressanten Feldern aussieht, dividiert man mit (n − k)! auch diese Vertauschungen heraus.

Formaler lässt sich dieser Sachverhalt auch so formulieren: Eine n-elementige Menge hat genau $\tbinom n k$ k-elementige Teilmengen. Aufgrund dieser Parallele wird die Menge aller k-elementigen Teilmengen einer Menge M gelegentlich auch mit $\tbinom M k$ bezeichnet. Mit dieser Schreibweise gilt dann für jede endliche Menge M:

$\left|{M\choose k}\right| = {\left|M\right| \choose k}.$

Beispiel

Die Anzahl der möglichen Ziehungen beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) lässt sich so berechnen:

${49 \choose 6} = 13\,983\,816.$

Der Kehrwert $\tfrac{1}{13\,983\,816}$ gibt dann die Wahrscheinlichkeit an, mit einem Tipp 6 Richtige zu erzielen. Die Wahrscheinlichkeit für 5 Richtige bei 6 aus 49 lässt sich jedoch nicht mehr durch einen einzelnen Binomialkoeffizienten berechnen. Stattdessen benötigt man die Hypergeometrische Verteilung, in deren Berechnung dann mehrere Binomialkoeffizienten ausgewertet werden müssen.

Kombinatorische Beweise

Die kombinatorische Deutung erlaubt auch einfache Beweise von Relationen zwischen Binomialkoeffizienten. Beispiel: Für $1\leq k\leq n$ gilt:

${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$

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\}$.

Ausdrücke mit Binomialkoeffizienten

Summen mit Binomialkoeffizienten

$\sum_{k=0}^n \binom nk = \binom n0 + \binom n1 + \dotsb + \binom nn = 2^n.$

Dieser Formel liegt ein kombinatorischer Sachverhalt zu Grunde. Die Summe aller Binomialkoeffizienten „n über …“ entspricht der Mächtigkeit der Potenzmenge einer n-elementigen Menge. Die Formel lässt sich auch aus dem binomischen Lehrsatz herleiten, indem man x = y = 1 setzt.

Summen mit alternierenden Binomialkoeffizienten

$\sum_{k=0}^n (-1)^k \binom nk = \binom n0 - \binom n1 + \binom n2 - \dotsb = 0$ für n > 0.

Diese Formel folgt für ungerade n aus der Symmetrie des Binomialkoeffizienten. Für beliebige n lässt sie sich aus dem binomischen Lehrsatz herleiten, indem x = 1 und y = − 1 (oder x = − 1 und y = 1) gesetzt wird.

Summe verschobener Binomialkoeffizienten

$\sum_{k=0}^m \binom{n+k}n = \binom nn + \binom{n+1}n + \dotsb + \binom{n+m}n = \binom{n+m+1}{n+1}$

Vandermondesche Identität

$\sum_{j=0}^k \binom mj \binom n{k-j} = \binom{m+n}k.$

Es gibt auch hier ein kombinatorisches Argument: Die rechte Seite entspricht der Anzahl von k-elementigen Teilmengen einer (m + n)-elementigen Menge von Kugeln. Man kann sich nun vorstellen, dass die Kugeln zwei verschiedene Farben haben: m Kugeln seien rot und n Kugeln grün. Eine k-elementige Teilmenge besteht dann aus einer gewissen Anzahl j von roten Kugeln und k − j vielen grünen. Für jedes mögliche j 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

$(1+x)^n = \sum_{k=0}^n \binom n k x^k,$

sowie Ansatz

(1 + x)^m(1 + x)ⁿ = (1 + x)^{m + n}

und Koeffizientenvergleich.

Binomialkoeffizienten in der Analysis

Verallgemeinerung

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

$\binom \alpha k = \begin{cases}\frac{\alpha (\alpha - 1)(\alpha - 2) \dotsm (\alpha - (k - 1))}{k!}, &\text{wenn } k>0\\ 1, &\text{wenn } k=0\\ 0, &\text{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 kombinatorischen Definition (also der Definition von $\tbinom{\alpha} {k}$ als die Anzahl aller k-elementigen Teilmengen einer festen α-elementigen Menge) überein, und für nichtnegative k mit der algebraischen Definition (also der Definition von $\tbinom\alpha k$ als das Produkt $\tfrac {\alpha}1 \cdot \tfrac{\alpha-1}2 \dotsm \tfrac{\alpha-(k-1)}k$).

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) (-2) \cdots (-k)}{k!} = (-1)^k.$

Für $\alpha\in\R\setminus\{-1,-2,-3,\ldots\}$ erlaubt die Betafunktion B(x,y) eine Erweiterung der Definition auf reelle x:

$\binom\alpha x=\frac{1}{(\alpha+1)\,\mathrm B(x+1,\alpha-x+1)}=\frac{\Gamma(\alpha+1)}{\Gamma(x+1)\,\Gamma(\alpha-x+1)},$

wobei Γ(x) die Gammafunktion bezeichnet. Ist dabei x oder α − x eine negative ganze Zahl, so ist der Wert der rechten Seite 0.

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

$\binom{-\alpha} k = (-1)^k \binom{\alpha+k-1}k$

angeben.

Für reelle Zahlen beim zweiten Parameter kann diese Relation auf

$\binom{-\alpha}x = \left(\cos(\pi x)+\sin(\pi x)\cot(\pi\alpha)\right)\binom{\alpha+x-1}x$

erweitert werden.

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

Binomische Reihen

Für $n\in\N_0$ und $z\in\C\setminus\{1\}$ mit $|z|\ge 1$ erhält man die Beziehung

$\sum_{k=0}^\infty\binom kn\frac1{z^{k+1}}=\sum_{k=n}^\infty\binom kn\frac1{z^{k+1}}=\frac{1}{(z-1)^{n+1}},$

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

Ist $|z|\le 1$, $z\ne-1$ sowie $\alpha\in\C$, konvergiert die folgende Reihe gemäß

$\sum_{k=0}^\infty\binom\alpha k z^k=(1+z)^\alpha.$

(Für exaktere Bedingungen für z und α lese man den entsprechenden Artikel.)

Summenausdruck für die Betafunktion

Eine weitere Beziehung kann man für alle $m,n\ge 0$ relativ einfach mit vollständiger Induktion beweisen,

$\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{m+k+1}=\dfrac{1}{(m+n+1)\displaystyle\binom{m+n}m},$

woraus unmittelbar die Symmetrie

$\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{m+k+1}=\sum\limits_{k=0}^m\binom mk\frac{(-1)^k}{n+k+1}$

folgt. Eine Verallgemeinerung für $z,s\in\C$ mit $-z,-s\notin\N$ und $s+z\ne-1$ lautet

$\sum\limits_{k=0}^\infty\binom sk\frac{(-1)^k}{z+k+1}=\dfrac{1}{(z+s+1)\displaystyle\binom{z+s}s}=\mathrm{B}(z+1,s+1).$

Gaußsche Produktdarstellung für die Gammafunktion

Damit ist für $-z\notin\{0,1,2,\dots,n\}$

$\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{z+k}=\frac{n!}{z\,(z+1)\,(z+2)\cdot...\cdot(z+n)}.$

Betrachtet man den Fall $\mathrm{Re}\,z>0$, ersetzt die Brüche in der Summe durch Integrale gemäß

$\frac1{z+k}=\int\limits_0^1 t^{z+k-1}\mathrm{d}t$

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

$\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{z+k}= \int\limits_0^1t^{z-1}(1-t)^n\mathrm{d}t= n^{-z}\int\limits_0^nt^{z-1}\left(1-\frac tn\right)^n\mathrm{d}t,$

wobei beim letzten Integral die Substitution $t\to t/n$ angewendet wurde. Anzumerken bleibt hierbei, dass man diese Art von Summenausdrücken mit entsprechenden bestimmten Integralen ersetzen kann, und sich die Eigenschaften dieser Summen ebenso gut durch Umformungen der Integrale erschließen lassen. Schließlich hat man die Gleichung

$\int\limits_0^nt^{z-1}\left(1-\frac tn\right)^n\mathrm{d}t=\frac{n^z\,n!}{z\,(z+1)\,(z+2)\cdot...\cdot(z+n)},$

woraus sich durch den Grenzübergang $n\to\infty$ direkt die Gaußsche Produktdarstellung der Gammafunktion,

$\Gamma(z)=\lim\limits_{n\to\infty}\frac{n^z\,n!}{z\,(z+1)\,(z+2)\dotsm(z+n)},$

ergibt.^[1]

Digammafunktion und Euler-Mascheroni-Konstante

Für $m,n\in\N$ mit $m\le n$ gilt

$\sum\limits_{k=1}^m\binom n{m-k}\frac{(-1)^{k-1}}k=\binom nm\sum\limits_{k=n-m+1}^n\frac 1 k,$

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

$\sum\limits_{k=1}^n\binom nk\frac{(-1)^{k-1}}k=\sum\limits_{k=1}^n\frac 1 k.$

Ersetzt man diese Summe durch die Reihe

$\sum\limits_{k=1}^\infty\binom xk\frac{(-1)^{k-1}}k=\psi(x+1)+\gamma$

mit der Euler-Mascheroni-Konstanten γ und der Digammafunktion ψ(x), hat man eine Interpolation für die Folge

$a_n=\sum\limits_{k=1}^n\frac1k$

gefunden.

Referenzen

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

Weblinks

 Wikibooks: Mathe für Nicht-Freaks: Binomialkoeffizient – Lern- und Lehrmaterialien

 Commons: Binomial coefficients – Sammlung von Bildern, Videos und Audiodateien

• Download von BigAl (Kleines, freies und plattformunabhängiges Programm, u. a. zur genauen Berechnung des Binomialkoeffizienten; mit Quelltext)
• Online-Berechnung beliebiger Binomialkoeffizienten
• Tool zur Online-Berechnung des Binomialkoeffizienten (benötigt kein JavaScript o.ä.)