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

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\leq q\leq 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 B(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)B(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)^{\alpha }$ 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
• Wolstenholme-Primzahl

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)