Mathe Genie Lexikon Binomialkoeffizient Erklärung Bedeutung und Formel

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 zwei Zahlen ab; wenn diese p und q sind, dann schreibt man den Binomialkoeffizienten "p über q" als

${p \choose q}$

Inhaltsverzeichnis

1 Definition

2 Beispiele

3 Berechnung

4 Binomische Reihe

5 Anwendung in der Kombinatorik

6 Optimierung der Auswertung von Binomialkoeffizienten

7 Siehe auch

8 Weblinks

Definition

Die einfachste Definition gilt für den Fall, dass p und q ganze Zahlen sind, wobei p ? 0 ist. In diesem Fall definiert man

${p \choose q} = \left\{ \begin{matrix} \frac{p!}{q!\cdot(p-q)!} & \mbox{für } 0\le q\le p\\ 0 & \mbox{für } q>p \\ 0 & \mbox{für } q<0 \end{matrix} \right.$

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

Eine Verallgemeinerung, die in der Analysis eine Rolle spielt, erhält man, wenn p eine beliebige reelle Zahl und q eine nichtnegative ganze Zahl ist. In diesem Fall ist

${p \choose q} = \left\{ \begin{matrix} \frac{p\cdot(p-1)\cdot(p-2)\cdot...\cdot (p-q+1)}{q!} & \mbox{für } q>0\\ 1 & \mbox{für } q=0 \end{matrix} \right.$

der Binomialkoeffizient "p über q". Diese Definition stimmt für nichtnegative ganzzahlige p und q mit der ersten überein.

Die Betafunktion $?(x, y)$ erlaubt eine Erweiterung der Definition auf reelle q, aber nur für q>-1 und p-q>-1:

${p \choose q}=\frac{1}{(p+1)\cdot\beta(q+1,p-q+1)}$

Beispiele

${5 \choose 3} = \frac{5!}{3! \cdot 2!} = \frac{5\cdot 4\cdot 3}{3!} = \frac{60}{6} = 10$

${3 \choose 5} = 0$

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

${-1 \choose n} = \frac{(-1)\cdot (-2)\cdots (-n)}{n!} = (-1)^n$

${p \choose 1} = p$

${p \choose p} = 1$

Berechnung

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

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

Beispiel:

${4 \choose 2} = {3 \choose 2} + {3 \choose 1} = {2 \choose 2} + {2 \choose 1} + {2 \choose 1} + {2 \choose 0} = 1 + 2* {2 \choose 1} + 1 = 2 + 2*({1 \choose 1} + {1 \choose 0})$

= 2 + 2*(1 + 1) = 2 + 4 = 6

Sie eignet sich zum Beispiel, um alle Binomialkoeffizienten für ein vorgegebenes k zu bestimmen, ein Schema dazu ist das Pascalsche Dreieck.

Diese Methode hat den Nachteil, das sie sehr aufwendig ist, und je nachdem viel Speicher verbrauchen kann.

Besser und schneller ist folgende Formel:

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

Beispiel:

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

Ein wissenschaftlicher Taschenrechner erspart in der Praxis durch die Funktionstaste "nCr" (n choose r) viel Tipparbeit:

Eingabe p-Wert, Taste "nCr", Eingabe q-Wert, Taste "=".

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) ?$ mit Entwicklungspunkt 0.

Beispiele

$(1+x)^2 = {2 \choose 0}x^0 + {2 \choose 1} x^1 + {2 \choose 2} x^2 = 1 + 2x + x^2$

(ein Spezialfall der ersten binomischen Formel)

$\frac{1}{1+x} = (1+x)^{-1} = \sum_{k=0}^\infty {-1 \choose k} x^k = \sum_{k=0}^\infty (-x)^k$

$\sqrt{1+x} = (1+x)^{1/2} = \sum_{k=0}^\infty {1/2 \choose k} x^k$

Anwendung in der Kombinatorik

Eine Anwendung des Binomialkoeffizienten in der Kombinatorik ist die Bestimmung der 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öglichkeiten, beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) zu ziehen, berechnen:

${49 \choose 6}=13.983.816$

Optimierung der Auswertung von Binomialkoeffizienten

Da die Fakultäten extrem schnell wachsen, ist es sinnvoll, Zähler und Nenner dadurch kleinzuhalten, indem man nach jeder Multiplikation kürzt:

${49 \choose 6}= \frac{49*48*47*46*45*44}{6*5*4*3*2*1} = \frac{2352}{30}*\frac{47*46*45*44}{4*3*2*1} = \frac{392*47*46*45*44}{5*4*3*2*1}$

$= \frac{18424}{20}*\frac{46*45*44}{3*2*1} = \frac{4606*46*45*44}{5*3*2*1} = \frac{211876}{15}*\frac{45*44}{2*1} = \frac{211876*45*44}{15*2*1}$

$= \frac{9534420}{30}*\frac{44}{1} = \frac{317814*44}{1*1} = 317814*44 = 13983816$

Dabei entstehen nicht so große Zahlen, als wenn man die beiden Produkte am Ende dividiert hätte:

${49 \choose 6}= \frac{49*48*47*46*45*44}{6*5*4*3*2*1} = \frac{10068347520}{720} = 13983816$

Bei ${49 \choose 6}$ mag das noch nicht so wichtig sein, aber die beiden Produkte können sehr groß werden. Bei naiver Implementation auf Computern kann es schnell zu einem Speicherüberlauf kommen, beispielsweise bei ${144 \choose 32}$ .

Siehe auch

Polynomialkoeffizient

Weblinks

http://www.jonelo.de/java/bigal_de.html
Kleines, freies und plattformunabhängiges Programm, u. a. zur genauen Berechnung des Binomialkoeffizienten (mit Java-Quelltext)

Dieser Artikel ( Binomialkoeffizient ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence.