Beweis einer Summenformel für Binomialkoeffizienten

Question

Aufgabe:

Kann mir jemand mit der folgenden Aufgabe helfen:

Beweise folgende Formel:

$$\sum_{k=0}^{n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right)\left(\begin{array}{ll}{m} & {-} & {n} \\ {n} & {-} & {k}\end{array}\right)=\left(\begin{array}{l}{m} \\ {n}\end{array}\right)$$ 

Tipp: Welche Bedeutung hat jeder Term? Genauer (Vgl. Englisches Original): Wie können die einzelnen Summanden interpretiert werden? 

Comments

Der Ansatz ist, das ganze über vollständige Induktion zu beweisen. Dabei ist es nicht immer wichtig, zu wissen, welche Bedeutungen jede einzelne Variable hat.

Aber alle Terme beschreiben einen Binomialkoeffizienten. Schau dir die Definition dazu an.

---

Das sieht nach einer etwas anderen Schreibweise für die "Vandermondesche Identität" aus. Wenn du danach googelst, solltest du fündig werden.

Answer 1

Welche Bedeutung hat jeder Term?

Binomialkoeffizient rechts: Anzahl aller n-elementigen Teilmengen einer Menge mit m Elementen.

1. Binomialkoeffizient links: Anzahl aller k-elementigen Teilmengen einer Menge mit n Elementen.

2. Binomialkoeffizient links: Anzahl aller k-n -elementigen Teilmengen einer Menge mit m-n Elementen.

Summenzeichen: k läuft von 0 bis n.

Daraus ergibt sich ein Beweis der obigen Summenformel ohne Rechnung.

[spoiler]

Unterteile die gegebene Menge mit m Elementen in zwei Teilmengen. Eine mit n Elementen T1, die andere mit den übrigen n-m Elementen T2.

Wenn du nun n-elementigen Teilmengen der gesamten Menge mit m Elementen betrachtest, können ihre Element aus den beiden Teilmengen stammen.

Man wählt einige Elemente aus T1 und die andern aus T2. Innerhalb von T1 und T2 kann man unabhängig voneinander die richtige Anzahl Elemente auswählen und hat so die Anzahl der n-elementigen Teilmengen der Gesamtmenge auf m Elementen bestimmt. Fertig.

Konkret zählst du nun links zusammen:

(Die Zahl der Teilmengen aus T1 mit 0 Elementen )*(Zahl der Teilmengen aus T2 mit n Elementen)

+

(Die Zahl der Teilmengen aus T1 mit 1 Element )*(Zahl der Teilmengen aus T2 mit n-1 Elementen)

+

(Die Zahl der Teilmengen aus T1 mit 2 Elementen )*(Zahl der Teilmengen aus T2 mit n-2 Elementen)

usw.

+

(Die Zahl der Teilmengen aus T1 mit n Elementen )*(Zahl der Teilmengen aus T2 mit 0 Elementen)
=

Zahl der Teilmengen aus der Gesamtmenge  mit n Elementen

Comments

Gibt das für m=n überhaupt einen Sinn?

Bist Du sicher, dass die Aufgabe so richtig ist?

---

Gibt das für m=n überhaupt einen Sinn?

Gute Anregung. Logischerweise müsste gelten: (m tief m) = 1

Kann sein, dass man nun noch Definitionen "erfinden" müsste.

Sagen wir mal: 0 Elemente aus der "leeren Menge" auswählen kann man ein mal.

1, 2, 3, ... Elemente aus der "leeren Menge" auswählen kann man null mal.

Kontrolliere mal mit dieser Idee.

---

Die original Formulierung wäre:

Also es ist schon richtig, was ich oben geschrieben habe. Hey Lu, ich lass mir deinen Rechenweg durch den Kopf gehen. Danke schon mal für die Erklärungen der Bedeutung von Elementen in der Gleichung.

---

Gut. Habe in der Fragestellung nun Hint explizit mit "Tipp" umgesetzt. Damit sollte klar sein, dass über die Bedeutung von "Binomialkoeffizienten" argumentiert werden soll. Schau dir in deinen Unterlagen die "Bedeutung" genau an. Du wirst das dann vermutlich auf Englisch formulieren müssen und da sollte auch auf Englisch etwas über die Anzahl von n-elementigen Teilmengen einer Menge mit m Elementen stehen.

---

Hallo Lu. Dein Vorschlag mit den Ts funktioniert vorerst prima. Danach aber, als ich dies durch vollständige Induktion zu Ende bringen will, klappt es auf einmal nicht. Es wäre sehr nett von dir, wenn du dir meinen Versuch ansehen würdest. Was mache ich da falsch?

---

Deine Umformung

ist falsch. T1 und T2 sind elementfremde Mengen. Du kannst nicht einfach Elemente aus T1 in T2 suchen, denn es gilt T1 u T2 = Grundmenge aus m Elementen und T1 n T1 = ∅ (leere Menge).

Daher:

Deine Behauptung (die ich gar nicht brauche) ist falsch.

1. Kommt k nicht vor.

2. Die Behauptung falsch.

Du müsstest noch ausschliessen, dass die n-Elementigen Teilmengen links nicht alle Elemente aus der kleineren Menge enthalten. Daher gibt das tendentiell links eher mehr als rechts.

3. Mein Beweis ist oben schon lange fertig. Man wählt Elemente aus der einen und dann dazu Elemente aus der zweiten Teilmenge, so dass es zusammen immer n Elemente sind. (Daher links in der Behauptung das Produkt unter dem Summenzeichen).

Genauer (Vgl. Englisches Original): Wie können die einzelnen Summanden interpretiert werden?

Du sollst interpretieren und nicht rechnen. D.h. meinen Text oben verstehen und halt auf Englisch formulieren. Vgl. meine Antwort und suche die korrekte Formulierung der Interpretation auf Englisch. Tippe sie ab und bastle mit den gleichen Worten den Beweis, wie in der Fragestellung verlangt.

---

Vandermondesche Identität

D.h. der Vorschlag von Trashcan, solltest du mit deinem Skript nicht klarkommen.

---

Bin am verzweifeln:

---

Du sollst interpretieren und nicht rechnen. D.h. meinen Text oben verstehen und halt auf Englisch formulieren. Vgl. meine Antwort und suche die korrekte Formulierung der Interpretation auf Englisch. Tippe sie ab und bastle mit den gleichen Worten den Beweis, wie in der Fragestellung verlangt.

---

Ok Lu. Vielen Dank. Ich dachte bloß, dass "Prove  the identity" -Beweise die Gleichung bedeutet-. Also die Vollständige Induktion ist sinnlos deiner Meinung nach. Ich werde es dann so machen wie du sagst

---

Würde ich so tun. Die Fragestellung so weit du sie auf Englisch gepostet hast, verlangt, dass du von der Interpretation der Summanden ausgehst. Da brauchst du keine vollständige Induktion, dafür euren Text mit der Interpretation der Binomialkoeffizienten.

Was hast du denn bei der "Vandermondeschen Identität" gefunden, die Trashcan oben erwähnt hat ? Kannst du als Zusatzaufgabe für dich durchgehen. 

---

Habe nichts brauchbares gefunden bei der "Vandermondeschen Identität", da ich noch keine Zeit hatte, sie näher unter der Luppe zu nehmen. Ich muss da sehr viele Statistik-Aufgaben lösen für die ich kurze und präzise Lösungen finden muss.

Vielen Dank dir

Dan

Answer 2

Aloha :)

Du hast \(m\) Objekte gegeben, von denen genau \(n\) "besondere" Objekte und genau \((m-n)\) "gewöhnliche" Objekte sind. \(\binom{n}{k}\) ist die Anzahl der Möglichkeiten, von den \(n\) besonderen Objekten genau \(k\) auszuwählen. \(\binom{m-n}{n-k}\) ist die Anzahl der Mögichkeiten, von den \((m-n)\) gewöhnlichen Objekten genau  \((n-k)\) auszuwählen. Die Situation ist hier also, dass von den \(m\) Objekten genau \(n\) ausgewählt werden sollen. Der Summand \(\binom{n}{k}\cdot\binom{m-n}{n-k}\) zählt die Möglichkeiten, dass unter den \(n\) ausgewählten Objekten genau \(k\) besondere und \((n-k)\) gewöhnliche Objekte sind. Die Summe aller dieser Möglichkeiten ist natürlich gleich der Gesamtzahl an Möglichkeiten, von \(m\) Objekten genau \(n\) auszuwählen, und das ist \(\binom{m}{n}\). Die Formel lässt sich daher durch "intensives Anschauen" beweisen ;)

Nee, im Ernst, der Beweis sollte über Induktion möglich sein. Wenn du dazu Hilfe benötigst, melde dich einfach nochmal.

Comments

Dein "intensives Anschauen" (=Bedeutung verwenden) ist wohl genau das, was erwartet wird, wenn im Zusammenhang mit dem Beweis gefragt wird:

Welche Bedeutung hat jeder Term?

Mit dem Rückgriff auf "die Bedeutung" kann schlimmstenfalls auch ein Induktionsbeweis in Worten geführt werden. Reines Rumrechnen mit Brüchen ist nur dann nötig, wenn "die Bedeutung der Binomialkoeffizienten" nicht genau oder anders als in der Kombinatorik eingeführt wurde.

---

Vielen Dank für deine Erklärung.

ich habe versucht die Induktion anzuwenden, aber es klappt ja nicht. Es scheitert schon beim einsetzen der ersten 2 Terme:

---

Warum?

(0 tief 0) = 1

(1 tief 0) = 1

(m tief 0) = 1

In der zweiten Zeile fehlt der zweite Summand. 1 + (m-1) = m .