Formelsammlung Lexikon Binomialkoeffizient


Startseite	Bookmark setzen Sitemap Impressum

» Formelsammlung:

» Startseite

» Astronomie

» Biologie

» BWL

» Chemie

» Informatik

» Mathematik

» Physik

» Interaktiv:

» Forum

» Lexikon

» Mitmachen

» Links zu Uns

» Surftipps

» Informationen:

» Kontakt

» Impressum

» Über Formel-Sammlung.de

» Partnerseiten:

www.schuelerlexikon.de

» Partner:

Etiketten
Kostenlose Kochrezepte
Künstler Verzeichnis
Schilder
Spieleforum
Witze & SMS Sprüche

Binomialkoeffizient

Sie befinden Sie in: Formelsammlung Lexikon > b > Binomialkoeffizient

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)

Lexikon Eintrag Drucken |

Dokument als PDF downloaden

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

zum Seitenanfang

» Unterstüzt von:

» Anzeigen: