Natürlichkeit des Binomialkoeffizienten

19.07.2008, 18:56

Mathe_2010?

Natürlichkeit des Binomialkoeffizienten

Guten Abend,

Ich würde gerne wissen, wie man beweisen kann, dass der Binomialkoeffizient n!/[(n-k)!*k!] stets eine natürliche Zahl ist.

Also der Quotient n!/k! ist auf jeden Fall natürlich (da k ja nie größer als n ist).
Es muss also gezeigt werden, dass das "restliche" Produkt von n! (also n! ohne die Faktoren von k!) restlos durch (n-k)! geteilt werden kann.
Hat dies vielleicht etwas mit Primzahlen zu tun?

Hmm..ich denke mal, ich machs wieder viel zu kompliziert und übersehe wieder irgendeine nahe liegende, triviale Lösung traurig

19.07.2008, 19:00

Leopold

Auf diesen Beitrag antworten »

Wenn du dir die Herkunft des Binomialkoeffizienten aus der Kombinatorik vor Augen hältst, ist die Ganzzahligkeit klar. Ansonsten beachte:

$\begin{eqnarray*} {n \choose 0} = {n \choose n} = 1 \end{eqnarray*}$

$\begin{eqnarray*} {n \choose {k-1}} + {n \choose k} = {{n+1} \choose k} \end{eqnarray*}$

19.07.2008, 19:15

Mathe_2010?

Auf diesen Beitrag antworten »

Richtig, die Binomialkoeffizienten ergeben sich ja duch Addition und müssen daher natürlich sein. Aber das war mir ja klar, mir geht es eigentlich nur um eine rein rechnerische Lösung. Also sowas wie:

n!/[(n-k)!*k!]=p ; n und k sind natürliche Zahlen und n>=k

Es soll jetzt gezeigt werden, dass p auch eine natürliche Zahl ist.
Gibt es vielleicht Rechengesetze für Fakultäten, mithilfe derer ich geieignet umformen kann?

19.07.2008, 19:20

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Mathe_2010?
Richtig, die Binomialkoeffizienten ergeben sich ja duch Addition und müssen daher natürlich sein.

So einfach ist es auch wieder nicht. Leopold wollte hier eine vollständige Induktion andeuten.

19.07.2008, 20:40

Mathe_2010?

Auf diesen Beitrag antworten »

Und wie kann ich hier einen Induktionsbeweis führen?

K ist ja keine "konstante" Variable, denn mit steigendem n steigt ja auch die Anzahl der Werte, die K annehmen kann, und für jeden dieser Fälle muss ja die Gültigkeit gezeigt werden...

19.07.2008, 20:52

tmo

Auf diesen Beitrag antworten »

Na und?
Wenn du bei der Induktionsvorraussetzung annimmst, dass der Wert für ein n und alle $\begin{eqnarray*} 0 \leq k \leq n \end{eqnarray*}$ natürlich ist, dann darfst du dies im Induktionsschritt verwenden, um zu zeigen, dass er dann auch für $\begin{eqnarray*} n+1 \end{eqnarray*}$ und alle $\begin{eqnarray*} 0 \leq k \leq n+1 \end{eqnarray*}$ natürlich ist.

20.07.2008, 01:16

outSchool

Auf diesen Beitrag antworten »

Beweis mit Induktion
@Mathe_2010

Zeige die Anfangsbedingung für n=1, k=1 also

$\begin{eqnarray*} \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \frac{1!}{0!(1-0)!} + \frac{1!}{1!(1-1)!} = \frac{2!}{1!(2-1)!} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow 1 + 1 = 2 \end{eqnarray*}$

$\begin{eqnarray*} \text{Zeige nun } n \to n+1 \end{eqnarray*}$

Beweise dazu die Gültigkeit des Bildungsgesetzes der Binomialkoeffizienten

$\begin{eqnarray*} \begin{pmatrix} n \\ k-1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n+1 \\ k \end{pmatrix} \end{eqnarray*}$

Siehe auch die Antwort von Leopold.

$\begin{eqnarray*} \begin{pmatrix} n \\ k-1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{(k-1)!(n-(k-1))!} + \frac{n!}{k!(n-k)!} = . . . = \begin{pmatrix} n+1 \\ k \end{pmatrix} \end{eqnarray*}$

Neue Frage »

Antworten »

Natürlichkeit des Binomialkoeffizienten

Verwandte Themen