Binomialkoeffizient Identität mit Summe

Question

Sei N aus den natürlichen Zahlen, und $$ n \in {1,...,N} $$ und $$s \in {0,1,....,N}$$ Zeige:

$$\sum \limits_{k=0}^{n} \begin{pmatrix} s\\k \end{pmatrix} * \begin{pmatrix} N-s\\n-k \end{pmatrix} = \begin{pmatrix} N\\n \end{pmatrix}$$

Ich komme hier irgendwie nicht auf das richtige Ergebnis, selbst nachdem ich alle mir bekannten Identitäten eingesetzt habe. Ich habe gesehen, dass dies die Vandermonde Identität ist trotzdem schaffe ich dies nicht

Comments

Hallo,

in dem Wikipedia-Artikel zur Vandermonde-Indentität finden sich mehrere Beweise. Such Dir einen aus und erkläre, was Du nicht verstehst.

Gruß

---

Hallo ,

ja mein Problem ist dass in den anderen ungleichungen , die Rechte Seite anders sussieht bzw. das nicht (N über n) steht.

Liebe Grüße

Answer 1

Aloha :)

\(\binom{N}{n}\) ist die Anzahl der Möglichkeiten, aus \(N\) Objekten genau \(n\) auszuwählen. Lege die \(N\) Objekte der Reihe nach nebeneinander. Wenn du von den ersten \(s\) Objekten der Reihe genau \(k\) auswählst, wofür es \(\binom{s}{k}\) Möglichkeiten gibt, musst du von den hinteren \((N-s)\) Objekten noch genau \((n-k)\) auswählen, wofür es \(\binom{N-s}{n-k}\) Möglichkeiten gibt. Macht insgesamt \(\binom{s}{k}\cdot\binom{N-s}{n-k}\) Möglichkeiten.

Da du aus den ersten \(s\) Objekten \(k=0\), \(k=1\), \(k=2\), ... oder \(k=s\) Objekte auszuwählen kannst, musst du diese Möglichkeiten noch summieren:$$\sum\limits_{k=0}^s\binom{s}{k}\cdot\binom{N-s}{n-k}=\binom{N}{k}$$

Wegen \(\binom{s}{k}=0\) für \(k>s\) kannst du die Summe über \(k\) auch bis \(n\) gehen lassen und erhältst dann die zu zeigende Behauptung.

Comments

Danke für den einfachen Lösungsweg !!