Binomialkoeffizient, Summe, < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:28 Fr 05.10.2012 | | Autor: | Lu- |
| Aufgabe | Man gebe einen kombinatorischen Beweis für die Binomialidentität:
[mm] \vektor{n+1 \\ k+1}= \sum_{m=k}^n \vektor{m \\ k} [/mm] |
Hallo ;))
[mm] \vektor{n+1 \\ k+1}.. [/mm] Anzahl aller k+1 elementigen Teilmengen einer n+1 elementigen Menge.
[mm] \sum_{m=k}^n \vektor{m \\ k} [/mm] .. Vereinigt alle k-elementigen Teilmengen, wobei die Anzahl der Elemente der Grundmenge jeweils um 1 erhöht wird.
Ich frag mich nun, warum die zwei Identitäten gleich sein sollen?
Weiß wer eine kombinatorische Überlegung dazu?
Auf Antworten würd ich mich freuen,
Mfg Lu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:20 Fr 05.10.2012 | | Autor: | abakus |
> Man gebe einen kombinatorischen Beweis für die
> Binomialidentität:
> [mm]\vektor{n+1 \\
k+1}= \sum_{m=k}^n \vektor{m \\
k}[/mm]
> Hallo
> ;))
> [mm]\vektor{n+1 \\
k+1}..[/mm] Anzahl aller k+1 elementigen
> Teilmengen einer n+1 elementigen Menge.
>
> [mm]\sum_{m=k}^n \vektor{m \\
k}[/mm] .. Vereinigt alle
> k-elementigen Teilmengen, wobei die Anzahl der Elemente der
> Grundmenge jeweils um 1 erhöht wird.
>
> Ich frag mich nun, warum die zwei Identitäten gleich sein
> sollen?
> Weiß wer eine kombinatorische Überlegung dazu?
>
> Auf Antworten würd ich mich freuen,
> Mfg Lu
Hallo Lu,
du kennst sicher aus dem Pascal'schen Dreieck den Zusammenhang
[mm]\vektor{m+1 \\
k+1}=\vektor{m \\
k}+\vektor{m +1\\
k}[/mm].
Kombinatorisch bedeutet das:
Wenn man aus n+1 Elementen k+1 Elemente auswählen will,
dann hat man entweder
in m Ziehungen schon k Elemente gewählt (und zieht im nächsten Versuch das (k+1)-te Element)
oder man hat in m Versuchen schon alle (k+1) Elemente gezogen (und zieht im nächsten Versuch kein weiteres).
Der letzte Summand [mm]\vektor{m +1\\
k}[/mm]
ist nun wiederum die Summe aus [mm]\vektor{m \\
k} und \vektor{m\\
k-1}[/mm].
Den letzten Summanden davon kann man wiederum zerlegen...
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:02 Di 16.10.2012 | | Autor: | Lu- |
Hallo, danke für die Antwort. Aber ich schaff dass leider nicht so und such deshalb einen anderen Lösungweg.
Kann man das vlt auch anschaulich erklären, anstatt mit Rekursiven Definitionen. Ich komme damit leider nicht zurrecht...
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:29 Di 16.10.2012 | | Autor: | luis52 |
Moin,
vielleicht hast du ja Zugang zu einer Universitaetsbibliothek.
Schau auf Seite 79-80 in
@book{chuan1992principles,
title={Principles and techniques in combinatorics},
author={Chuan-Chong, C. and Koh, K.M. and Khee-Meng, K.},
year={1992},
publisher={World Scientific Publishing Company Incorporated}
}
vg Luis
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:58 Do 18.10.2012 | | Autor: | Lu- |
Danke, jap ich habe ein Bibliothek in meiner Näher ;)
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:16 Mi 24.10.2012 | | Autor: | Lu- |
Hallo,
sry ich hatte erst jetzt Zeit mir das nochmal genau anzusehen:
[mm] \vektor{n+1 \\ k+1}= \vektor{n\\ k+1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
= [mm] \vektor{n-1 \\ k+1}+\vektor{n-1 \\ k}+\vektor{n \\ k}
[/mm]
[mm] =\vektor{n-2\\ k+1}+\vektor{n-2 \\ k}+\vektor{n-1 \\ k}+\vektor{n-1 \\ k}+\vektor{n \\ k}
[/mm]
[mm] =..=\vektor{k \\ k}...\vektor{n-2\\ k}+\vektor{n-2 \\ k}+\vektor{n-1 \\ k}+\vektor{n-1 \\ k}+\vektor{n \\ k}
[/mm]
SO meintest du das?
Leider bin ich mir beim letzten Schritt nicht so ganz sicher, ob da nicht noch ein Binomialkoeffizient [mm] \vektor{k \\ k+1} [/mm] bleibt, der ja sowieso 0 ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Fr 26.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
