Erzeugende Funkion,summenindex < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:45 Mo 11.02.2013 | | Autor: | quasimo |
| Aufgabe | Wir betrachten die Rekursion für die Triangulierung (vollständige Zerlegung eines n-ecks in Dreiecke) des (n+2) Ecks.
Wobei wir die Rekursion für n Ecke hergeleitet haben: f(n).. Anzahl der Triangulierungen eines n Ecks: f(n) = [mm] \sum_{k=2}^{n-1} [/mm] f(k) f(n-k+1) für n [mm] \ge [/mm] 3 |
Nun hab ich eine Frage , beim beweis:
Wieso gilt:
[mm] \sum_{n\ge3} \sum_{k=0}^{n-3} [/mm] f(k+2) f(n-k-1) [mm] z^n [/mm] = [mm] \sum_{k\ge0} \sum_{n=k+3}^\infty [/mm] f(k+2) f(n-k-1) [mm] z^n [/mm]
Was wird hier genau gemacht?
Nur die Summenindices verändern sich.
??
|
|
| |
|
Hallo quasimo,
da wird einfach nur umgeordnet.
> Wir betrachten die Rekursion für die Triangulierung
> (vollständige Zerlegung eines n-ecks in Dreiecke) des
> (n+2) Ecks.
> Wobei wir die Rekursion für n Ecke hergeleitet haben:
> f(n).. Anzahl der Triangulierungen eines n Ecks: f(n) =
> [mm]\sum_{k=2}^{n-1}[/mm] f(k) f(n-k+1) für n [mm]\ge[/mm] 3
> Nun hab ich eine Frage , beim beweis:
> Wieso gilt:
>
> [mm]\sum_{n\ge3} \sum_{k=0}^{n-3}[/mm] f(k+2) f(n-k-1) [mm]z^n[/mm] = [mm]\sum_{k\ge0} \sum_{n=k+3}^\infty[/mm] f(k+2) f(n-k-1) [mm]z^n[/mm]
>
> Was wird hier genau gemacht?
> Nur die Summenindices verändern sich.
Na, eben. Nehmen wir mal geordnete Paare (n,k) in Betracht.
Auf der linken Seite werden die wie folgt durchlaufen (zeilenweise zu lesen):
(3,0);
(4,0); (4,1);
(5,0); (5,1); (5,2);
(6,0); (6,1); (6,2); (6;3) etc.
Auf der rechten Seite stehen die gleichen (n,k)-Paare, nur wird die obige Auflistung spaltenweise durchlaufen.
Und das wars dann auch schon.
Grüße
reverend
|
|
|
|
