Beweis Binomialkoeffizient, richtig?

17.04.2011, 15:00

mr.cat

Beweis Binomialkoeffizient, richtig?

Liebe Mathe-Freunde,

ich muss einige Beweise für Binomialkoeffizienten aufstellen, bei einem Beweis bin ich mir nicht ganz sicher.

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

Ich habe es erstmal andersrum geschrieben:

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

jetzt habe ich die Definition genommen und das ganze mit Fakultät geschrieben

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

dann habe ich den rechten Bruch mit k erweitert, damit ich gleiche Nenner habe:

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

Nun habe ich das (n+1)! anders geschrieben und den Zähler zusammengefasst:

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

Jetzt kommt die Frage wo ich nicht genau weiß ob ich das ganze richtig mache:

Kann ich einfach das

(n+1-k) im Zähler mit dem Nenner kürzen und dann steht im Nenner praktisch nur (n-k)? So dass daraus folgt:

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

Damit wäre der Beweis ja gemacht oder habe ich irgendwo einen Rechenfehler?

Vielen Dank für eure Bemühung smile

17.04.2011, 15:09

Merlinius

Auf diesen Beitrag antworten »

Ist korrekt. Schöner ist es zwar oft, wenn man mit einem anfängt und versucht, es so umzuformen, dass man das andere stehen hat, aber formal richtig ist es natürlich.

17.04.2011, 15:13

mr.cat

Auf diesen Beitrag antworten »

Zitat:

Original von Merlinius
Ist korrekt. Schöner ist es zwar oft, wenn man mit einem anfängt und versucht, es so umzuformen, dass man das andere stehen hat, aber formal richtig ist es natürlich.

Danke für die Antwort smile

Meinst du dass ich am Anfang das nicht hätte "andersherum" schreiben sollen? also das n über k nicht alleine auf die linke Seite stellen?

Das komische ist: so habe ich es erst versucht, aber dann habe ich folgende Gleichung bei gleichem Nenner:

n! * (k(n-k)+1)*(n+1)= (n+1)!

Da kam ich nicht mehr weiter Big Laugh

17.04.2011, 15:17

Merlinius

Auf diesen Beitrag antworten »

Zitat:

Original von mr.cat

Zitat:

Original von Merlinius
Ist korrekt. Schöner ist es zwar oft, wenn man mit einem anfängt und versucht, es so umzuformen, dass man das andere stehen hat, aber formal richtig ist es natürlich.

Also, ich meinte, dass man es so aufschreibt:

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

Sieht halt besser aus als $\begin{eqnarray*} A = B \Leftrightarrow ... \Leftrightarrow 0 = 0 \end{eqnarray*}$

Aber das ist auch nicht so wichtig. Dein Beweis ist korrekt, also passt es doch.

17.04.2011, 15:23

mr.cat

Auf diesen Beitrag antworten »

Ah ok vielen Dank.

Noch eine kurze Frage:

Wie kann ich einen formal korrekten Beweis bringen, dass die Anzahl der Permutationen von n verschiedenen Elementen n! ist?

Es erscheint so einfach, dass ich nicht weiß, wie ich es aufschreiben soll...

PS: die Fragen haben mehr was mit Kombinatorik zu tun, das merke ich gerade.
Ich mache halt die Grundlagen der Analysis und daher wusste ich nicht genau wo dieser Thread am besten aufgehoben ist, bitte dies zu verzeihen - wenn ich dies ins falsche Unterforum gestellt habe smile

17.04.2011, 15:47

Merlinius

Auf diesen Beitrag antworten »

Das beweist man am besten mit vollständiger Induktion. Eine Permutation ist ja eine bijektive Selbstabbildung einer Menge.

Also "unsauber" kann man es natürlich argumentativ recht leicht begründen.

Ein sauberer Beweis könnte so aussehen, dass man sagt, eine Menge X mit n Elementen ist isomorph zur Menge $\begin{eqnarray*} \{1, ..., n\} \end{eqnarray*}$ , also betrachtet man nur die Permutationen auf dieser Menge (genannt symmetrische Gruppe $\begin{eqnarray*} S_n \end{eqnarray*}$ ). Der Induktionsanfang ist klar. Im Induktionsschritt betrachtet man nun also die Permutationen einer n+1-elementigen Menge. Diese kann man partitionieren in n+1 "Gruppierungen" von Permutationen. Wobei dann die i-te Gruppierung $\begin{eqnarray*} G_i \end{eqnarray*}$ jeweils aus allen Permutationen besteht, die das i-te Element an die Position n+1 schiebt. Insgesamt hat man also n+1 "Gruppierungen". Dann kann man mit der Induktionsvoraussetzung zeigen, dass alle dieser $\begin{eqnarray*} G_i \end{eqnarray*}$ die Mächtigkeit n! haben, und da sie untereinander disjunkt sind, hat man insgesamt (n+1)·n! = (n+1)! Permutationen der (n+1)-elementigen Menge.

Neue Frage »

Antworten »

Beweis Binomialkoeffizient, richtig?

Verwandte Themen