Binomialkoeffizient
aus Freepedia, der freien Wissensdatenbank
| Bild:Qsicon Ueberarbeiten.png | Dieser Artikel bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit, ihn zu verbessern und entferne anschließend diese Markierung. |
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 <math>n</math> und <math>k</math> ab. Der Binomialkoeffizient "<math>n</math> über <math>k</math>" wird als
- <math>{n \choose k}</math></center>
geschrieben.
Inhaltsverzeichnis |
Definition
Für nichtnegative ganze Zahlen <math> n, k\in\N_0 </math> mit <math>0\leq k \leq n</math> und <math>n\neq 0</math> wird der Binomialkoeffizient "n über k" durch
- <math>{n \choose k} = \frac{n!}{k!\cdot (n-k)!} = \frac n 1 \cdot \frac{n-1}{2}\cdot\ldots\cdot \frac{n-k+1}{k} = \prod_{i=1}^k \frac {n-(i-1)} i</math>
definiert. Für alle anderen ganzen Zahlen <math>n, k</math> wird <math>{n \choose k}=0</math> definiert.
Dabei bezeichnet <math> n! = n \cdot(n-1)\cdot \dots \cdot 2 \cdot 1</math> die Fakultät von <math>n</math> (<math>0! = 1</math>).
Eigenschaften
- <math>{n \choose k}</math> ist stets eine nichtnegative ganze Zahl.
- Direkt aus der Definition und anschaulich aus dem Pascalschen Dreieck folgt:
- <math>{n \choose n-k} = {n \choose k}</math>,
- <math>{n \choose 0} = {n \choose n} = 1</math> und
- <math>{n \choose 1} = {n \choose n-1} = n</math>.
- Bricht man die Produktdarstellung von <math>{n \choose k} = \prod_{i=1}^k \frac{n-(i-1)}{i}</math> nach dem <math>l</math>-ten Glied ab, erhält man den Binomialkoeffizient <math>{n \choose l} = \prod_{i=1}^l \frac{n-(i-1)}{i}</math>.
- Es gelten die Beziehungen:
- <math>{n-1 \choose k-1} + {n-1 \choose k} = {n \choose k}</math>,d.h. addiert man im Pascalschen Dreieck zwei benachbarte Zahlen einer Zeile, erhält man den Wert in der darunterliegenden Zeile zwischen beiden Zahlen.
- <math>\sum_{k=0}^n {n \choose k} = {n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n</math>,d.h. addiert man alle Binomialkoeffizienten „n über ...“ erhält man die Mächtigkeit einer n-elementigen Potenzmenge.
- <math>\sum_{k=0}^n (-1)^k \cdot {n \choose k} = {n \choose 0} - {n \choose 1} + {n \choose 2} - \cdots = 0</math>, das bedeutet anschaulich, dass das Pascalsche Dreieck symmetrisch ist, speziell wenn <math>n</math> ungerade ist, man <math>0</math> als Ergebnis erhält, wenn man die Elemente links in einer Zeile von denen rechts abzieht.
- <math>\sum_{k=0}^m {n+k \choose n} = {n \choose n} + {n+1 \choose n} + \cdots + {n+m \choose n} = {n+m+1 \choose n+1}</math>, dies erhält man leicht durch Iteration der ersten hier aufgeführten Beziehung.
- <math> k \cdot {n \choose k} = n \cdot {n-1 \choose k-1}</math> folgt direkt aus der Definition des Binomialkoeffizienten und der Fakultät.
- <math>\sum_{j=0}^k {m \choose j}{n \choose k-j} = {m+n \choose k}</math>
Die letzte Gleichung ist bekannt als Vandermondesche Identität.
Herleitung ausgewählter Eigenschaften
- <math>{n-1 \choose k-1}+{n-1 \choose k}={n \choose k}</math>
- <math>{n-1 \choose k-1}+{n-1 \choose k}</math><math>=\frac{(n-1)!}{(k-1)!(n-1-k+1)!}+\frac{(n-1)!}{k!(n-1-k)!}</math><math>=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!(n-k)}{k!(n-k)!}</math><math>=\frac{k(n-1)!}{k!(n-k)!}+\frac{n!-k(n-1)!}{k!(n-k)!}</math><math>=\frac{n!}{k!(n-k)!}</math><math>={n \choose k}</math>
- <math>\sum\limits^n_{k=0}{n \choose k}=2^n</math>
- Induktionsbeginn:<math>\sum\limits^1_{k=0}{1 \choose k}={0 \choose 1}+{1 \choose 1}=2^1</math>
- Induktionsschritt:<math>\sum\limits^{n+1}_{k=0}{n+1 \choose k}</math><math>={n+1 \choose 0}+{n+1 \choose n+1}+\sum\limits^{n}_{k=1}{n+1 \choose k}</math><math>=2+\sum\limits^{n}_{k=1}{n+1 \choose k}</math><math>=2+\sum\limits^{n}_{k=1}\left({n \choose k-1}+{n \choose k}\right)</math><math>=2+\sum\limits^{n}_{k=1}{n \choose k-1}+\sum\limits^{n}_{k=1}{n\choose k}</math><math>=2+\sum\limits^{n-1}_{k=0}{n \choose k}+\sum\limits^{n}_{k=1}{n \choose k}</math><math>=2+\sum\limits^{n}_{k=0}{n \choose k}-{n \choose n}+\sum\limits^{n}_{k=0}{n \choose k}-{n \choose 0}</math><math>=2+\sum\limits^{n}_{k=0}{n \choose k}-1+\sum\limits^{n}_{k=0}{n \choose k}-1</math><math>=2\sum\limits^{n}_{k=0}{n \choose k}</math><math>=2\cdot 2^n=2^{n+1}</math>
- <math>\sum\limits^{n}_{k=0}(-1)^k{n \choose k}=0</math>
- Fall 1: k ungerade: <math>n=2m+1</math>
- <math>\sum\limits^{n}_{k=0}(-1)^k{n \choose k}</math><math>=\sum\limits^{m}_{k=0}\left({n \choose 2k}-{n \choose 2k+1}\right)</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m}_{k=0}{n \choose 2k+1}</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m}_{k=0}{n \choose n-2k-1}</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m}_{k=0}{n \choose 2m+1-2k-1}</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m}_{k=0}{n \choose 2(m-k)}</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m}_{k=0}{n \choose 2k}=0</math>
- Fall 2: k ungerade: <math>n=2m</math>
- <math>\sum\limits^{n}_{k=0}(-1)^k{n \choose k}</math><math>=\sum\limits^{m}_{k=0}{n \choose 2k}-\sum\limits^{m-1}_{k=0}{n \choose 2k+1}</math><math>=2+\sum\limits^{m-1}_{k=1}{n \choose 2k}-\sum\limits^{m-1}_{k=0}{n \choose 2k+1}</math><math>=2+\sum\limits^{m-1}_{k=1}\left({n-1 \choose 2k-1}+{n-1 \choose 2k}\right)-\sum\limits^{m-1}_{k=0}\left({n-1 \choose 2k}+{n-1 \choose 2k+1}\right)</math><math>=2+\sum\limits^{m-1}_{k=1}{n-1 \choose 2k-1}+\sum\limits^{m-1}_{k=0}{n-1 \choose 2k}-{n-1\choose 0}-\sum\limits^{m-1}_{k=0}{n-1 \choose 2k}-\sum\limits^{m-1}_{k=0}{n-1 \choose 2k+1}</math><math>=1+\sum\limits^{m-1}_{k=1}{n-1 \choose 2k-1}-\sum\limits^{m-1}_{k=0}{n-1 \choose 2k+1}</math><math>=1+\sum\limits^{m-1}_{k=1}{n-1 \choose 2k-1}-\sum\limits^{m}_{k=1}{n-1 \choose 2(k-1)+1}</math><math>=1+\sum\limits^{m-1}_{k=1}{n-1 \choose 2k-1}-\sum\limits^{m-1}_{k=1}{n-1 \choose 2k-1}-{n-1 \choose n-1}=0</math>
- <math>\sum\limits^{m}_{k=0}{n+k \choose n}={n+m+1 \choose n+1}</math>
- Induktionsbeginn: <math>\sum\limits^{1}_{k=0}{n+k \choose n}={n \choose n} + {n+1 \choose n}=\frac{n!}{n!}+\frac{(n+1)!}{n!}</math><math>=\frac{(n+1)!+(n+1)!(n+1)}{(n+1)!}</math><math>=\frac{(n+1)!(n+2)}{(n+1)!}</math>=<math>\frac{(n+2)!}{(n+1)!}={n+2 \choose n+1}</math>
- Induktionsschritt: <math>\sum\limits^{m+1}_{k=0}{n+k \choose n}</math><math>={n+m+1 \choose n}+\sum\limits^{m}_{k=0}{n+k \choose n}</math><math>={n+m+1 \choose n}+{n+m+1 \choose n+1}</math><math>=\frac{(n+m+1)!}{n!(m+1)!}+\frac{(n+m+1)!}{(n+1)!m!}</math><math>=\frac{(n+m+1)!(m+1)+(n+m+1)!(n+1)}{(n+1)!(n+2)!}</math><math>=\frac{(n+m+1)!(m+n+2)}{(n+1)!(n+2)!}</math><math>=\frac{(n+m+2)!}{(n+1)!(n+2)!}</math><math>={n+(m+1)+1 \choose n+1}</math>
Berechnung, Algorithmus
Für die Berechnung empfiehlt es sich, die Ganzzahligkeit der Zwischenprodukte geschickt auszunutzen, indem immer im Wechsel eine Multiplikation und eine Division ausgeführt werden. Ein Beispiel ist
- <math>{49 \choose 6}= (((((49\cdot 48)/2\cdot 47)/3\cdot 46)/4\cdot 45)/5\cdot 44)/6</math>,
und wir wissen, dass alle auftretenden Divisionen ohne Rest aufgehen; alle Zwischenergebnisse sind natürliche Zahlen und wachsen auch nicht unnötig an.
Im Fall <math>k > n/2</math> wird die Berechnung geschickt durch Ausnutzung der Beziehung
- <math>{n\choose k}={n\choose n-k}</math>
verkürzt.
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
- <math>{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</math>
- <math>{3 \choose 5} = 0</math>, <math>{n \choose 1} = n</math>, <math>{n \choose n} = 1</math>
Der Binomialkoeffizient in der Kombinatorik
Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine zentrale Rolle, denn <math>n\choose k</math> ist die Anzahl der Möglichkeiten, aus einer Menge mit <math>n</math> Elementen <math>k</math> 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 <math>n!</math> alle möglichen Vertauschungen, suche sich <math>k</math> „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 Vertauschungen unter diesen <math>k</math> Elementen mit <math>k!</math> heraus. Da es auch keine Rolle spielt, wie die Anordnung auf den uninteressanten Feldern aussieht, dividiert man mit <math>(n-k)!</math> auch diese Vertauschungen heraus.
Formaler lässt sich dieser Sachverhalt auch so formulieren: Eine <math>n</math>-elementige Menge hat genau <math>n\choose k</math> <math>k</math>-elementige Teilmengen. Aufgrund dieser Parallele wird die Menge aller <math>k</math>-elementigen Teilmengen einer Menge <math>M</math> gelegentlich auch mit <math>M\choose k</math> bezeichnet. Mit dieser Schreibweise gilt dann für jede endliche Menge <math>M</math>:
- <math>\left|{M\choose k}\right| = {\left|M\right| \choose k}</math>
Beispiel
Die Anzahl der möglichen Ziehungen beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) lässt sich so berechnen:
- <math>{49 \choose 6}=13.983.816</math>
Der Kehrwert 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 <math>1\leq k\leq n</math> gilt:
- <math>{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}</math>
Beweis: Es sei <math>X</math> eine <math>n</math>-elementige Menge und <math>x\in X</math> ein festes Element. Dann zerfallen die <math>k</math>-elementigen Teilmengen von <math>X</math> in zwei Klassen:
- die Teilmengen, die <math>x</math> enthalten; sie bestehen also aus <math>x</math> zusammen mit einer <math>(k-1)</math>-elementigen Teilmenge der <math>(n-1)</math>-elementigen Menge <math>X\setminus\{x\}</math>
- die Teilmengen, die <math>x</math> nicht enthalten; sie sind <math>k</math>-elementige Teilmengen der <math>(n-1)</math>-elementigen Menge <math>X\setminus\{x\}</math>.
Rekursive Darstellung und Pascalsches Dreieck
Für den Binomialkoeffizienten nichtnegativer ganzer Zahlen <math> n </math> und <math> k </math> hat man folgende rekursive Darstellung:
- <math>{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}</math>
Diese Formel eignet sich auch, um alle Binomialkoeffizienten bis zu einer vorgegebenen Schranke für <math>n</math> 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. Den Koeffizienten <math> n \choose k </math> findet man dabei in der <math> (n+1) </math>-ten Zeile, an der <math> (k+1) </math>-ten Stelle:
Verallgemeinerung
Eine Verallgemeinerung, die in der Analysis eine Rolle spielt, erhält man, wenn man für <math>n</math> eine beliebige reelle oder komplexe Zahl <math> \alpha </math> zulässt, aber <math> k </math> weiterhin als ganzzahlig voraussetzt. In diesem Fall ist
- <math> {\alpha \choose k} =
\begin{cases}\frac{\alpha (\alpha - 1)(\alpha - 2) \cdots (\alpha - k + 1)}{k!} &\mbox{wenn } k\ge 0\\ 0 &\mbox{wenn } k<0 \end{cases}</math> der Binomialkoeffizient "<math> \alpha </math> über <math> k </math>" (das leere Produkt im Fall <math> k=0 </math> ist definiert als 1). Diese Definition stimmt für nichtnegative ganzzahlige <math> \alpha </math> mit der ersten überein.
Beispielsweise ist
- <math>{2{,}5 \choose 2} = \frac{2{,}5\cdot 1{,}5}{2!} = \frac{3{,}75}{2} = 1{,}875</math>
und
- <math>{-1 \choose k} = \frac{(-1)\cdot (-2)\cdots (-k)}{k!} = (-1)^k.</math>
Für <math> \alpha\in\mathbb R\setminus\{-1,-2,-3,\ldots\} </math> erlaubt die Betafunktion <math>\mathrm B(x,y)</math> eine Erweiterung der Definition auf reelle <math> k </math>:
- <math>{\alpha \choose k}=\frac{1}{(\alpha+1)\cdot\mathrm B(k+1,\alpha-k+1)}</math>
(Ist dabei <math>k</math> oder <math>\alpha-k</math> 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
