Formel für Binomialkoeffizienten

29.10.2019, 01:30

Merle150

Formel für Binomialkoeffizienten

Meine Frage:
Also es ist ja

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

Aber ehrlich gesagt verstehe ich nicht, wie man darauf durch doppeltes Abzählen kommt. Auch der Hinweis, dass man unterscheiden soll ob das Element $\begin{eqnarray*} n+1 \end{eqnarray*}$ in der Teilmenge enthalten ist oder nicht, bringt mich nicht weiter.

Meine Ideen:
Könntet ihr mir bitte helfen? Wie habt ihr den Beweis verstanden?

Ich verstehe ihn einfach nicht, und das wurmt mich

29.10.2019, 07:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Merle150
Auch der Hinweis, dass man unterscheiden soll ob das Element $\begin{eqnarray*} n+1 \end{eqnarray*}$ in der Teilmenge enthalten ist oder nicht, bringt mich nicht weiter.

Jammerschade, denn genau das "bringt" es doch:

Man pickt sich irgendein Element der $\begin{eqnarray*} (n+1) \end{eqnarray*}$ -elementigen Grundmenge $\begin{eqnarray*} M \end{eqnarray*}$ heraus, nennen wir es $\begin{eqnarray*} e \end{eqnarray*}$ . Die Restmenge sei dann $\begin{eqnarray*} M'=M\setminus\{e\} \end{eqnarray*}$ bezeichnet, die enthält genau $\begin{eqnarray*} n \end{eqnarray*}$ Elemente.

Jetzt zählen wir die $\begin{eqnarray*} k \end{eqnarray*}$ -elementigen Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ :

1) Da sind die, welche $\begin{eqnarray*} e \end{eqnarray*}$ nicht enthalten. Das sind dann offenbar die $\begin{eqnarray*} k \end{eqnarray*}$ -elementigen Teilmengen von $\begin{eqnarray*} M' \end{eqnarray*}$ , davon gibt es $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ .

2) Alle anderen enthalten dann $\begin{eqnarray*} e \end{eqnarray*}$ . Außer $\begin{eqnarray*} e \end{eqnarray*}$ besitzen diese Teilmengen genau $\begin{eqnarray*} (k-1) \end{eqnarray*}$ Elemente, die sämtlich aus $\begin{eqnarray*} M' \end{eqnarray*}$ stammen müssen, dafür gibt es $\begin{eqnarray*} \binom{n}{k-1} \end{eqnarray*}$ Auswahlen.

Beide Anzahlen summiert bekommt man $\begin{eqnarray*} \binom{n}{k-1}+\binom{n}{k} = \binom{n+1}{k} \end{eqnarray*}$ .

P.S.: In der Rangliste der idiotischen Sprüche steht "bringt mich nicht weiter" ganz weit oben. Der wird immer gebetsmühlenartig vorgetragen und ist in gefühlt 99% der Fälle falsch.

29.10.2019, 07:51

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
P.S.: In der Rangliste der idiotischen Sprüche steht "bringt mich nicht weiter" ganz weit oben. Der wird immer gebetsmühlenartig vorgetragen und ist in gefühlt 99% der Fälle falsch.

Dein Gefühl trügt dich. Es sind >99,7182818 %.

29.10.2019, 14:59

Merle150

Auf diesen Beitrag antworten »

Nun habe ich es verstanden, danke! smile

Und ihr habt auch beide recht, was den Satz "bringt mich nicht weiter" betrifft, habe mich blöd angestellt

Neue Frage »

Antworten »

Formel für Binomialkoeffizienten

Verwandte Themen