Binomialidentität < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:45 So 13.05.2012 | | Autor: | clemenum |
| Aufgabe | Man geben bitte einen rein kombinatorischen Beweis (d.h. nicht durch Einsetzen in die Definition und/oder Induktion) folgender Binomialidentität:
${n+1 [mm] \choose [/mm] k+1} = [mm] \sum_{m= k }^n {m\choose k} [/mm] $ |
So, bei meiner Lösungsidee kann ich mal folgendes sagen:
Die linke Seite ist einfach die Anzahl aller $k+1-$elementigen Teilmengen einer $n+1$ elementigen Menge. Die rechte Seite bildet "oder - Verknüpfungen", vereinigt also alle k-elementigen Teilmengen, wobei die Anzahl der Elemente in der Grundmenge jeweils um eins ansteigt und von k bis n geht. Ich vereinige also alle Mengen auf der rechten Seite von m = k bis n. Ich sehe aber leider überhaupt nicht, warum das zur Gleichheit führen soll.
Gelingt es vielleicht mit geeigneten Färbungen ? Ich kann es nicht machen, in dem ich z.B. ein beliebiges aber festes Element $a$ betrachte und dann die Fälle (a aus einer Teilmenge, a nicht aus einer Teilmenge) betrachte. Das ginge doch nur, wenn ich auf zwei Summanden aufspalte. Außerdem würde sich bei letzterer Methode auch die Elementanzahl in den Teilmengen verringern.
Kann mir jemand einen Tipp geben, wie ich weiter kommen könnte, wäre euch sehr dankbar! 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:59 So 13.05.2012 | | Autor: | luis52 |
Moin,
ich habe mal fuer $n=5$ und $k=2$ bzw. $k=3$ die $k+1$-elementigen Teilmengen der $n+1$-elementigen Menge [mm] $\{1,2,3,4,5,6\}$ [/mm] bestimmt.
Es soll ja gelten $20=1+3+6+10$ bzw. $15=1+4+10$.
Ich weiss nicht ob das tragfaehig ist, aber *ich* sehe die relevanten Zahlen.
vg Luis
| 1: |
| | 2: | [,1] [,2] [,3]
| | 3: | [1,] 4 5 6
| | 4: | [2,] 3 5 6
| | 5: | [3,] 3 4 6
| | 6: | [4,] 3 4 5
| | 7: | [5,] 2 5 6
| | 8: | [6,] 2 4 6
| | 9: | [7,] 2 4 5
| | 10: | [8,] 2 3 6
| | 11: | [9,] 2 3 5
| | 12: | [10,] 2 3 4
| | 13: | [11,] 1 5 6
| | 14: | [12,] 1 4 6
| | 15: | [13,] 1 4 5
| | 16: | [14,] 1 3 6
| | 17: | [15,] 1 3 5
| | 18: | [16,] 1 3 4
| | 19: | [17,] 1 2 6
| | 20: | [18,] 1 2 5
| | 21: | [19,] 1 2 4
| | 22: | [20,] 1 2 3
| | 23: |
| | 24: | [,1] [,2] [,3] [,4]
| | 25: | [1,] 3 4 5 6
| | 26: | [2,] 2 4 5 6
| | 27: | [3,] 2 3 5 6
| | 28: | [4,] 2 3 4 6
| | 29: | [5,] 2 3 4 5
| | 30: | [6,] 1 4 5 6
| | 31: | [7,] 1 3 5 6
| | 32: | [8,] 1 3 4 6
| | 33: | [9,] 1 3 4 5
| | 34: | [10,] 1 2 5 6
| | 35: | [11,] 1 2 4 6
| | 36: | [12,] 1 2 4 5
| | 37: | [13,] 1 2 3 6
| | 38: | [14,] 1 2 3 5
| | 39: | [15,] 1 2 3 4
|
|
|
|
|
