Binomialkoeffizient < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:42 Di 22.03.2011 | | Autor: | Mandy_90 |
| Aufgabe | Man beweise folgende Eigenschaft der Binomialkoeffizienten einmal durch ein kombinatorisches Abzählargument und einmal durch einen geeignet gewählten Koeffizientenvergleich:
[mm] \vektor{m+n \\ k}=\summe_{j=0}^{k} \vektor{m \\ j}*\vektor{n \\ k-j}.
[/mm]
Was ergibt sich im spezialfall n=m=k ? |
Hallo zusammen^^
Ich habe versucht das zu beweisen, aber ich komme nicht mehr weiter.
Im Spezialfall ergibt sich einfach [mm] \vektor{2n \\ n}=\summe_{j=0}^{n} (\vektor{n \\ j})^{2}.
[/mm]
Jetzt soll ich die Behauptung zunächst durch ein kombinatorisches Abzählargument beweisen. Ich weiß nicht, ob mein Ansatz zu einem solchen Argument gehört, aber ich hab einfach versucht die Summe umzuschreiben:
[mm] \summe_{j=0}^{k} \vektor{m \\ j}*\vektor{n \\ k-j}=\vektor{n \\ k}+m*\vektor{n \\ k-1}+\vektor{m \\ 2}\vektor{n \\ k-2}+\vektor{m \\ k}.
[/mm]
Weiter komme ich hier leider nicht, ich hab schon gesucht, ob ich irgendeine Rechenregel für Binomialkoeffizienten finde, die mich weiterbringen könnte, aber ich hab nichts gefunden.
Wäre lieb, wenn mir jemand weiterhelfen könnte.
Vielen Dank
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:49 Di 22.03.2011 | | Autor: | abakus |
> Man beweise folgende Eigenschaft der Binomialkoeffizienten
> einmal durch ein kombinatorisches Abzählargument und
> einmal durch einen geeignet gewählten
> Koeffizientenvergleich:
>
> [mm]\vektor{m+n \\ k}=\summe_{j=0}^{k} \vektor{m \\ j}*\vektor{n \\ k-j}.[/mm]
>
> Was ergibt sich im spezialfall n=m=k ?
> Hallo zusammen^^
>
> Ich habe versucht das zu beweisen, aber ich komme nicht
> mehr weiter.
>
> Im Spezialfall ergibt sich einfach [mm]\vektor{2n \\ n}=\summe_{j=0}^{n} (\vektor{n \\ j})^{2}.[/mm]
>
> Jetzt soll ich die Behauptung zunächst durch ein
> kombinatorisches Abzählargument beweisen.
Linker Term: Anzahl der Möglichkeiten, k Elemente aus (m+n) Elementen auszuwählen.
Rechte Seite: Die m+n Elemente werden in zwei disjunkte Teilmengen mit m bzw n Elementen zerlegt. Die Auswahl der k Elemente ist nun wie folgt möglich:
0 Elemente aus der ersten und k Elemente aus der zweiten Teilmenge wählen
1 Element aus der ersten und k-1 Elemente aus der zweiten Teilmenge wählen
2 Elemente aus der ersten und k-2 Elemente aus der zweiten Teilmenge wählen
...
...
alle k Elemente nur aus der ersten Teilmenge wählen
Gruß Abakus
> Ich weiß nicht,
> ob mein Ansatz zu einem solchen Argument gehört, aber ich
> hab einfach versucht die Summe umzuschreiben:
>
> [mm]\summe_{j=0}^{k} \vektor{m \\ j}*\vektor{n \\ k-j}=\vektor{n \\ k}+m*\vektor{n \\ k-1}+\vektor{m \\ 2}\vektor{n \\ k-2}+\vektor{m \\ k}.[/mm]
>
> Weiter komme ich hier leider nicht, ich hab schon gesucht,
> ob ich irgendeine Rechenregel für Binomialkoeffizienten
> finde, die mich weiterbringen könnte, aber ich hab nichts
> gefunden.
> Wäre lieb, wenn mir jemand weiterhelfen könnte.
>
> Vielen Dank
> lg
|
|
|
|
