Binomialkoeffizienten

19.12.2004, 01:49

Y-G

Binomialkoeffizienten

Hallo!
Ich habe mich gerade mit den Binomialkoeffizeinten ein wenig auseinandergesetzt. Aber irgendwie stehe ich jetzt auf der Leitung.
Wie begründet man, dass $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{(n-k)!*k!} \end{eqnarray*}$ (mit $\begin{eqnarray*} n, k \in \mathbb N, n\geq k \end{eqnarray*}$ ) eine ganze Zahl ist? Für mich ist es irgendwie nicht so trivial, wie es anscheinend sonst auf allen Internetseiten der Fall ist.

Danke im Voraus!

19.12.2004, 13:09

Leopold

Auf diesen Beitrag antworten »

Zunächst einmal kannst du ja $\begin{eqnarray*} (n-k)! \end{eqnarray*}$ kürzen:

$\begin{eqnarray*} {n \choose k} = \frac{n \cdot (n-1) \cdot (n-2) \cdots (n-k+1)}{k!} \end{eqnarray*}$

Und die einfachste Methode, sich klarzumachen, daß es sich hier um eine ganze Zahl handelt, ist, diese kombinatorisch zu interpretieren. Will man nämlich die Möglichkeiten zählen, aus $\begin{eqnarray*} n \end{eqnarray*}$ Elementen $\begin{eqnarray*} k \end{eqnarray*}$ mit Berücksichtigung der Anordnung herauszugreifen, so findet man für das erste Element $\begin{eqnarray*} n \end{eqnarray*}$ Möglichkeiten, für das zweite $\begin{eqnarray*} n-1 \end{eqnarray*}$ , für das dritte $\begin{eqnarray*} n-2 \end{eqnarray*}$ usw., insgesamt also $\begin{eqnarray*} n \cdot (n-1) \cdot (n-2) \cdots (n-k+1) \end{eqnarray*}$ Möglichkeiten. Wenn man die Anordnung aber nicht berücksichtigen will, so muß man jeweils $\begin{eqnarray*} k! \end{eqnarray*}$ der bisherigen Anordnungen identifizieren (nämlich diejenigen, die durch eine Permutation auseinander hervorgehen). Und so kommt man auf den in Rede stehenden Bruch. Und da dieser eine Anzahl angibt, muß er ganzzahlig sein.

20.12.2004, 10:09

klarsoweit

Auf diesen Beitrag antworten »

Man könnte sich auch überlegen, dass in dem Zähler von dem Ausdruck
$\begin{eqnarray*} {n \choose k} = \frac{n \cdot (n-1) \cdot (n-2) \cdots (n-k+1)}{k!} \end{eqnarray*}$
k aufeinanderfolgende natürliche Zahlen stehen. Eine davon ist also durch k teilbar, eine andere durch k-1 usw. Auf diese Weise läßt sich das k! komplett rauskürzen.
Besonders toll ist der Beweis aber nicht. Ich würde es mit vollständiger Induktion machen und dabei die Regel
$\begin{eqnarray*} {n \choose k} + {n \choose k + 1} = {n + 1 \choose k + 1} \end{eqnarray*}$
verwenden.

20.12.2004, 10:50

JochenX

Auf diesen Beitrag antworten »

also anschaulich finde ich das mit dem herauskürzen sehr gut.....

aber ganz bewiesen isses allein mit der aussage nicht: so ist z.b. auch bei (16*7)/(2*4*8) jede nennerzahl durch eine zählerzahl teilbar, aber es kommt eben keine ganze zahl raus...

mfg jochen

20.12.2004, 11:30

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
so ist z.b. auch bei (16*7)/(2*4*8) jede nennerzahl durch eine zählerzahl teilbar, aber es kommt eben keine ganze zahl raus...

Es muss ja auch andersrum sein... Augenzwinkern

20.12.2004, 13:46

JochenX

Auf diesen Beitrag antworten »

nun gut, da hastdu recht... aber wenn ich das ganze jetzt einfach stürze (also zähler nenner vertauschen, weil das kennt sonst wieder keiner), ist dann mein einwand nicht gerechtfertigt?

20.12.2004, 14:14

klarsoweit

Auf diesen Beitrag antworten »

der Einwand ist teilweise richtig. Ich habe ja auch gemeint, dass in dem Zähler von dem besagten Ausdruck k aufeinanderfolgende natürliche Zahlen stehen. Davon ist genau eine durch k teilbar. Der Vorgänger ist durch k - 1 teilbar, usw. Wenn man in der Kette "vorne" angekommen ist, macht man "hinten" weiter. Kein Faktor wird beim Kürzen mehr als einmal angefaßt. Natürlich ist das kein wirklich guter Beweis, falls man das als Beweis überhaupt gelten lassen will. Es ist aber eine stimmige anschauliche Überlegung.

20.12.2004, 14:35

etzwane

Auf diesen Beitrag antworten »

Ich denke schon, das diese Argumentation als 'Beweisführung' geeignet ist.
Wenn nicht, muss man nur noch einen Mathematiker finden, der diese Beweisführung so umformuliert, dass sie auch von einem Mathematiker akzeptiert wird.
Dadurch ändert sich aber an dem Sachverhalt nichts, da aus k hintereinander folgenden natürlichen Zahlen immer eine Zahl durch eine der Zahlen 1,2,3 usw. bis k ohne Rest teilbar ist, oder ?

20.12.2004, 14:38

Leopold

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{17 \cdot 16 \cdot 15 \cdot 14 \cdot 13}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \end{eqnarray*}$

In der Tat: Einer der Faktoren im Zähler ist durch 5 teilbar, nämlich 15. Aber der Vorgänger 14 ist nicht durch 4 teilbar und 13 nicht durch 3, ...

20.12.2004, 14:41

etzwane

Auf diesen Beitrag antworten »

ein gutes Beispiel sagt immer noch mehr als 1000 Worte ...

20.12.2004, 15:44

Auf diesen Beitrag antworten »

Noch einfacher:

$\begin{eqnarray*} {7\choose 3}=\frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \end{eqnarray*}$ Augenzwinkern

20.12.2004, 16:13

JochenX

Auf diesen Beitrag antworten »

also einigen wir uns darauf, das diese argumentationsweise nicht korrekt ist und doch ein induktionsbeweis ansteht?!

20.12.2004, 19:06