Binomialkoeffizient ausrechnen

20.10.2012, 18:41

Mixer007

Binomialkoeffizient ausrechnen

Hallo, ich hab eine Frage zu den Binomialkoeffizienten:

Und zwar wenn ich jetzt den Binomialkoeffizient von ( 29,6) berechnen will, wie gehe ich dann vor? Also ich kann das ja so schreiben:

29!/ (6! ( 29-6)! ) aber das dauert ja ewig bis man das berechnet hat?

Wie gehe ich da jetzt am besten vor, wenn ich große Binomialkoeffizienten berechnen will?

20.10.2012, 18:48

Dopap

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient ausrechnen

Zitat:

Original von Mixer007

29!/ (6! ( 29-6)! ) aber das dauert ja ewig bis man das berechnet hat?

kürzen !

$\begin{eqnarray*} \binom {29}{6}=\frac { 29 \cdot 28 \cdot 27 \cdots 24}{ 2\cdot 3 \cdot 4 \cdot 5 \cdot 6} \end{eqnarray*}$

und wenn man will nochmal kürzen

20.10.2012, 19:52

Mixer007

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient ausrechnen
aber gibts da keine Formel für sowas oder geht das tatsächlich nur durch kürzen?

20.10.2012, 20:26

Dopap

Auf diesen Beitrag antworten »

das ist die Formel. Einfacher geht es nicht.

20.10.2012, 20:35

Mixer007

Auf diesen Beitrag antworten »

aber das dauert trotzdem nochmal ne ganze Zeit.

Wenn ich jetzt kürz kommt ja das raus:

$\begin{eqnarray*} 29*14*9*6*5*8*24*23*22*21 *** 1/ ( 1) \end{eqnarray*}$

bis man das jetzt ausrechnet dauert es auch, was kann ich da jetzt machen?

20.10.2012, 20:49

Dopap

Auf diesen Beitrag antworten »

dein Latex ist so nicht lesbar. Kürzen geht bis auf eine 5 im Nenner. Aber egal.

Was heisst hier Zeit ? Mit dem Taschenrechner geht das in 10 Sekunden.

edit: sorry vertippt, keine 5 im Nenner!

20.10.2012, 20:55

Mixer007

Auf diesen Beitrag antworten »

ich muss ohne taschenrechner das berechnen Big Laugh

20.10.2012, 21:42

Leopold

Auf diesen Beitrag antworten »

Das geht ohne Taschenrechner! Am besten merkt man sich die viel einfachere Formel

$\begin{eqnarray*} {n \choose k} = \frac{(n)_k}{k!} \end{eqnarray*}$

Das Pochhammer-Symbol $\begin{eqnarray*} (n)_k \end{eqnarray*}$ im Zähler stellt ein Produkt mit $\begin{eqnarray*} k \end{eqnarray*}$ Faktoren dar, mit $\begin{eqnarray*} n \end{eqnarray*}$ beginnend, jeder weitere Faktor um $\begin{eqnarray*} 1 \end{eqnarray*}$ kleiner als sein Vorgänger. In Zähler und Nenner stehen also rücklaufende Produkte mit $\begin{eqnarray*} k \end{eqnarray*}$ Faktoren, im Zähler beginnt man mit $\begin{eqnarray*} n \end{eqnarray*}$ und im Nenner mit $\begin{eqnarray*} k \end{eqnarray*}$ selbst.

Wie Dopap schon gesagt hat, läuft das im konkreten Beispiel auf

$\begin{eqnarray*} {{29} \choose 6} = \frac{29 \cdot 28 \cdot 27 \cdot 26 \cdot 25 \cdot 24}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \end{eqnarray*}$

Es ist $\begin{eqnarray*} 4 \cdot 6 = 24 \end{eqnarray*}$ , also kann man die $\begin{eqnarray*} 24 \end{eqnarray*}$ wegkürzen, die $\begin{eqnarray*} 5 \end{eqnarray*}$ kürzt man gegen die $\begin{eqnarray*} 25 \end{eqnarray*}$ , die $\begin{eqnarray*} 3 \end{eqnarray*}$ gegen die $\begin{eqnarray*} 27 \end{eqnarray*}$ und die $\begin{eqnarray*} 2 \end{eqnarray*}$ gegen die $\begin{eqnarray*} 26 \end{eqnarray*}$ . Es verbleibt

$\begin{eqnarray*} {{29} \choose 6} = 29 \cdot 28 \cdot 9 \cdot 13 \cdot 5 \end{eqnarray*}$

Aus der $\begin{eqnarray*} 28 \end{eqnarray*}$ zieht man die $\begin{eqnarray*} 2 \end{eqnarray*}$ zur $\begin{eqnarray*} 5 \end{eqnarray*}$ herüber. Dann hat man noch, die Faktoren der Größe nach geordnet:

$\begin{eqnarray*} 29 \cdot 14 \cdot 13 \cdot 10 \cdot 9 \end{eqnarray*}$

Man rechnet im Kopf $\begin{eqnarray*} 9 \cdot 13 = 117 \end{eqnarray*}$ und im Kopf $\begin{eqnarray*} 29 \cdot 14 = 30 \cdot 14 -14 = 10 \cdot 3 \cdot 14 - 14 = 420 - 14 = 406 \end{eqnarray*}$

und schriftlich mit Papier und Bleistift (oder, wer's kann, im Kopf): $\begin{eqnarray*} 406 \cdot 117 = 47502 \end{eqnarray*}$ . Und das ganze noch mal $\begin{eqnarray*} 10 \end{eqnarray*}$ :

$\begin{eqnarray*} {{29} \choose 6} = 475020 \end{eqnarray*}$

Das ist also in polynomialer Zeit lösbar.

Neue Frage »

Antworten »

Binomialkoeffizient ausrechnen

Verwandte Themen