komb. beweis < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:31 Sa 03.11.2007 | | Autor: | AriR |
| Aufgabe | zeigen sie:
[mm] \summe_{k=0}^n\vektor{n \\ k}^2=\vektor{2n \\ n} [/mm] |
hey leute
ich schaffe es irgendwie nicht die summe aufzulösen.
ich komme, wenn ich mit der linken seite anfange, höchstens auf
[mm] \summe_{k=0}^n\bruch{n^2*(n-1)^2*...*(n-k+1)^2}{k!}
[/mm]
wenn ich mit der rechten seite anfange höchstens auf:
[mm] \bruch{(n+n)*(n + n-1)*...*(n+1)}{n!}
[/mm]
weiß einer von euch mit welchem der ansätze ich vllt weitermachen kann oder wie man das überhaupt zeigen kann?
danke und gruß ;)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:49 Sa 03.11.2007 | | Autor: | TottiIII |
Hallo
du sollst da denke ich nichts auflösen.
Du sollst "einfach" mit kombinatorischen Mitteln argumentieren und so zeigen dass die Formel gilt.
Ich bin aber im Moment auch noch nicht schlauer als du  .
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:53 Sa 03.11.2007 | | Autor: | max3000 |
Das ganze riecht mir nach vollständiger Induktion über n.
|
|
|
| |
|
> zeigen sie:
>
> [mm]\summe_{k=0}^n\vektor{n \\ k}^2=\vektor{2n \\ n}[/mm]
> hey
> leute
>
> ich schaffe es irgendwie nicht die summe aufzulösen.
>
> ich komme, wenn ich mit der linken seite anfange, höchstens
> auf
>
> [mm]\summe_{k=0}^n\bruch{n^2*(n-1)^2*...*(n-k+1)^2}{k!}[/mm]
>
>
> wenn ich mit der rechten seite anfange höchstens auf:
>
> [mm]\bruch{(n+n)*(n + n-1)*...*(n+1)}{n!}[/mm]
>
>
> weiß einer von euch mit welchem der ansätze ich vllt
> weitermachen kann oder wie man das überhaupt zeigen kann?
>
> danke und gruß ;)
Für einen rein kombinatorischen Beweis benutze folgende Überlegung: Zähle die Anzahl Möglichkeiten, aus einer $2n$-elementigen Menge $M$ eine $n$-elementige Teilmenge auszuwählen, auf zwei Arten.
Die übliche Art der Zählung wäre zu sagen, dass es [mm] $\binom{2n}{n}$ [/mm] Möglichkeiten gibt (dies ist gerade die rechte Seite der zu beweisenden Gleichung).
Nun kann man aber diese $2n$-elementige Menge auch in zwei gleichgrosse (also je $n$-elementige) Mengen, sagen wir [mm] $M_1$ [/mm] und [mm] $M_2$ [/mm] disjunkt zerlegen: [mm] $M=M_1\cup M_2$. [/mm] Sei $k$ die Anzahl derjenigen Elemente, die bei einer konkreten Auswahl von insgesamt $n$ Elementen aus [mm] $M_1\cup M_2$ [/mm] aus der Menge [mm] $M_1$ [/mm] gewählt werden. Dann müssen, um insgesamt $n$ Elemente auszuwählen, aus [mm] $M_2$ [/mm] genau $n-k$ Elemente ausgewählt werden. Die Gesamtzahl der Möglicheiten, aus der $2n$-elementigen Menge $M$ genau $n$ Elemente auszuwählen, erhält man, indem man $k$ von $0$ bis $n$ laufen lässt und aufsummiert: dies ergibt, unter Verwendung von [mm] $\binom{n}{k}^2=\binom{n}{k}\cdot\binom{n}{n-k}$, [/mm] die linke Seite der zu beweisenden Gleichung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:18 Sa 03.11.2007 | | Autor: | luis52 |
Hallo Somebody,
dein Beweis ist zucker!
lg Luis
PS: Deine Idee kann auch fuer den Beweis der folgenden
Verallgemeinerung angewandt werden:
[mm] $\sum_{k=0}^n{n\choose k}{m-n\choose n-k}={m\choose k}$.[/mm]
|
|
|
|
