Binomialkoeffizient

In der Mathematik sind Binomialkoeffizienten bestimmte ganze Zahlen, die in vielen Bereichen, wie zum Beispiel in der Kombinatorik und der Analysis, auftreten.

Ein Binomialkoeffizient hängt von zwei Zahlen $n$ und $k$ ab. Er wird mit dem Symbol ${n \choose k}$ geschrieben und als „ $n$ über $k$ “, „ $k$ aus $n$ “ oder „ $n$ tief $k$ “ gesprochen.

Den Namen erhielten diese Zahlen, da sie als Koeffizienten in den Potenzen des Binoms (Summe zweier Monome) (x+y) auftreten, es gilt der sog. Binomische Lehrsatz

(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}\cdot y^{k}

.

Satz

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

{n \choose k}={\frac {n}{1}}\ \cdot \ {\frac {n-1}{2}}\ \cdot \ \dots \ \cdot \ {\frac {n-k+1}{k}}={\frac {n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{k!}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}}

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, so kann man die aus der Kombinatorik bekannte Definition verwenden:

{n \choose k}={\frac {n!}{k!\cdot (n-k)!}}

Dabei gilt insbesondere auch

{n \choose 0}=1

Eigenschaften

Für nichtnegative ganze Zahlen $n$ und $k$ ist ${n \choose k}$ stets eine nichtnegative ganze Zahl.

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+1 \choose k+1}={n \choose k}+{n \choose 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 ist. Den Koeffizienten $n \choose k$ findet man dabei in der $(n+1)$ -ten Zeile, an der $(k+1)$ -ten Stelle:

Multiplikative Rekursion

Bricht man die Produktdarstellung von ${n \choose k}=\prod _{i=1}^{k}{\frac {n-(i-1)}{i}}$ nach dem $l$ -ten Glied ab, erhält man den Binomialkoeffizient ${n \choose l}=\prod _{i=1}^{l}{\frac {n-(i-1)}{i}}$ .

Summeneigenschaften

Aus dem binomischen Lehrsatz und der binomischen Reihe bzw. durch vollständige Induktion leitet man folgende Beziehungen ab:
- $\sum _{k=0}^{n}{n \choose k}={n \choose 0}+{n \choose 1}+\dots +{n \choose n}=2^{n}$ ,d.h. addiert man alle Binomialkoeffizienten „n über ...“ erhält man die Mächtigkeit einer n-elementigen Potenzmenge.
- $\sum _{k=0}^{n}(-1)^{k}\cdot {n \choose k}={n \choose 0}-{n \choose 1}+{n \choose 2}-\dots =0$ für $n>0$ . Für ungerade $n$ folgt das bereits aus der Symmetrie.
- $\sum _{k=0}^{m}{n+k \choose n}={n \choose n}+{n+1 \choose n}+\dots +{n+m \choose n}={n+m+1 \choose n+1}$
- $k\cdot {n \choose k}=n\cdot {n-1 \choose k-1}$ folgt direkt aus der Definition des Binomialkoeffizienten und der Fakultät.
- $\sum _{j=0}^{k}{m \choose j}{n \choose k-j}={m+n \choose k}$

Die letzte Gleichung ist bekannt als Vandermondesche Identität.

Algorithmus zur effizienten Berechnung

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

{n \choose k}=\prod _{i=1}^{k}{\frac {n+1-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 return 1
2  wenn 2k > n
3      dann führe aus ergebnis  $\leftarrow$  binomialkoeffizient(n, n-k)
4      sonst führe aus ergebnis  $\leftarrow$  n
5          von i  $\leftarrow$  2 bis k
6              führe aus ergebnis  $\leftarrow$  ergebnis  $\cdot$  (n + 1 - i)
7                        ergebnis  $\leftarrow$  ergebnis : i
8  return ergebnis

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

Der Binomialkoeffizient in der Kombinatorik

Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine zentrale Rolle, denn $n \choose 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 (6 z.B. 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 erreignet 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 $n \choose k$ $k$ -elementige Teilmengen. Aufgrund dieser Parallele wird die Menge aller $k$ -elementigen Teilmengen einer Menge $M$ gelegentlich auch mit $M \choose 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 ${\frac {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\}$ .

Verallgemeinerung

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

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

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

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)\cdot \dots \cdot (-k)}{k!}}=(-1)^{k}.

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

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

(Ist dabei $k$ oder $\alpha -k$ eine negative ganze Zahl, so ist der Wert der rechten Seite 0.)

Siehe auch

Weblinks

Download von BigAl (Kleines, freies und plattformunabhängiges Programm, u. a. zur genauen Berechnung des Binomialkoeffizienten; mit Java-Quelltext)
Online-Berechnung beliebiger Binomialkoeffizienten