Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Binomial aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

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\; \backslash 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=\backslash sum\_\{k=0\}^n\; \{n\; \backslash choose\; k\}x^\{n-k\}\; \backslash cdot\; y^k$.

Der Binomialkoeffizient $\{n\; \backslash choose\; k\}$ gibt die Anzahl der $k$-elementigen Teilmengen einer Menge mit $n$ Elementen an.

Definition

Für eine reelle Zahl n und eine nichtnegative ganze Zahl k ist der Binomialkoeffizient ?n über k? auf folgende Weise definiert:
:$\{n\; \backslash choose\; k\}\; =\; \backslash frac\; n\; 1\; \backslash \; \backslash cdot\; \backslash \; \backslash frac\{n-1\}\{2\}\; \backslash \; \backslash cdot\; \backslash \; \backslash dots\; \backslash \; \backslash cdot\; \backslash \; \backslash frac\{n-k+1\}\{k\}\; =\; \backslash frac\{n\; \backslash cdot\; (n-1)\; \backslash cdot\; \backslash dots\; \backslash cdot\; (n-k+1)\}\{k!\}\; =\; \backslash prod\_\{i=1\}^k\; \backslash 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\; \backslash choose\; k\}\; =\; \backslash frac\{n!\}\{k!\; \backslash cdot\; (n-k)!\}$

Eigenschaften

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

Rechenregeln

:$\{n\; \backslash choose\; 0\}\; =\; 1\; \backslash qquad\; \{n\; \backslash choose\; 1\}\; =\; n\; \backslash qquad\; \{n\; \backslash choose\; n\}\; =\; 1$
:$\{n\backslash choose\; n-k\}\; =\; \{n\backslash choose\; k\}$
:$\{n+1\; \backslash choose\; k+1\}\; =\; \{n\; \backslash choose\; k\}\; +\; \{n\; \backslash choose\; k+1\}$
:$k\; \backslash cdot\; \{n\; \backslash choose\; k\}\; =\; n\; \backslash cdot\; \{n-1\; \backslash choose\; k-1\}$

Summen von Binomialkoeffizienten

:$\backslash sum\_\{k=0\}^n\; \{n\; \backslash choose\; k\}\; =\; \{n\; \backslash choose\; 0\}\; +\; \{n\; \backslash choose\; 1\}\; +\; \backslash dots\; +\; \{n\; \backslash choose\; n\}\; =\; 2^n$
Dieser Regel liegt ein kombinatorischer Sachverhalt zu Grunde. Dies Summe aller Binomialkoeffizienten ?n über ...? entspricht der Mächtigkeit der Potenzmenge einer $n$-elementigen Menge.

:$\backslash sum\_\{k=0\}^n\; (-1)^k\; \backslash cdot\; \{n\; \backslash choose\; k\}\; =\; \{n\; \backslash choose\; 0\}\; -\; \{n\; \backslash choose\; 1\}\; +\; \{n\; \backslash choose\; 2\}\; -\; \backslash dots\; =\; 0$ für $n>0$. Für ungerade $n$ folgt das bereits aus der Symmetrie.
:$\backslash sum\_\{k=0\}^m\; \{n+k\; \backslash choose\; n\}\; =\; \{n\; \backslash choose\; n\}\; +\; \{n+1\; \backslash choose\; n\}\; +\; \backslash dots\; +\; \{n+m\; \backslash choose\; n\}\; =\; \{n+m+1\; \backslash choose\; n+1\}$
;Vandermondesche Identität : $\backslash sum\_\{j=0\}^k\; \{m\; \backslash choose\; j\}\{n\; \backslash choose\; k-j\}\; =\; \{m+n\; \backslash choose\; k\}$

Rekursive Darstellung und Pascalsches Dreieck

Für den Binomialkoeffizienten nichtnegativer ganzer Zahlen $n$ und $k$ hat man folgende rekursive Darstellung:
:$\{0\; \backslash choose\; 0\}\; =\; 1;\backslash quad\; \{n\; \backslash choose\; n\}\; =\; \{n\; \backslash choose\; 0\}\; =\; 1;\backslash quad\; \{n+1\; \backslash choose\; k+1\}\; =\; \{n\; \backslash choose\; k\}\; +\; \{n\; \backslash 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\; \backslash choose\; k$ findet man dabei in der $(n+1\; )$-ten Zeile, an der $(k+1)$-ten Stelle:

Algorithmus zur effizienten Berechnung

Für ganzzahlige $n$ existiert ein effizienter Algorithmus, der die Produktformel
:$\{n\; \backslash choose\; k\}\; =\; \backslash prod\_\{i=1\}^k\; \backslash 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\backslash choose\; n-k\}\; =\; \{n\backslash 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 $\backslash leftarrow$ binomialkoeffizient(n, n-k)
4 sonst führe aus ergebnis $\backslash leftarrow$ n
5 von i $\backslash leftarrow$ 2 bis k
6 führe aus ergebnis $\backslash leftarrow$ ergebnis $\backslash cdot$ (n + 1 - i)
7 ergebnis $\backslash leftarrow$ ergebnis : i
8 return ergebnis


Der Binomialkoeffizient in der Kombinatorik

Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine zentrale Rolle, denn $n\backslash 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\backslash choose\; k$ $k$-elementige Teilmengen. Aufgrund dieser Parallele wird die Menge aller $k$-elementigen Teilmengen einer Menge $M$ gelegentlich auch mit $M\backslash choose\; k$ bezeichnet. Mit dieser Schreibweise gilt dann für jede endliche Menge $M$:

:$\backslash left/\text{'}>\{M\backslash choose\; k\}\backslash right|\; =\; \{\backslash left|M\backslash right|\; \backslash choose\; k\}$

Beispiel

Die Anzahl der möglichen Ziehungen beim deutschen Quelltext)
• Online-Berechnung beliebiger Binomialkoeffizienten

       VIDEO-NEWS UND ANGEBOTE