rekursion in 2 Paramenter löse < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo
Ich habe eine rekursiv definierte Funktion:
f(N,n) = f(N-n,n) + f(N-1,n-1) mit $N,n \in \mathbb{N}_{>0}$.
Dabei ist f(N,1) = f(0,1) = f(n,n) = 1 ( Bem. f(0,0) = 1 )
und f(N,0) = 0 für N > 0
und für n > N ist f(N,n) = 0
Die brauche ich aber explizit, habe mich aber noch nie wirklich mit der Lösung von Rekusionen auseinandergestzt.
Ich habe versucht das ganze mit Erzeugendenfunktionen zu lösen
Zuerst die Rekursion bzgl. N:
$f(N,n)z^N = f(N-n)z^N + f(N-1,n-1)z^N = z^nf(N-n,n)z^{N-n} + zf(N-1,n-1)z^{N-1}$
Die erzeugende Funktion ist also:
$F_n(z) = \sum_{N=0}^\infty{f(N,n)z^N$
$ = z^n \sum_{N=n}^\infty{f(N,n)}z^N + z \sum_{N=n-1}^\infty{f(N,n-1)z^N$
$ = z^n F_n(z) + zF_{n-1}(z) $
$\Leftrightarrow F_n(z) = \frac{z}{1-z^n}F_{n-1}(z) $
Wegen f(0,0)=1 und f(N,0) = 0 für N>0 ist
$F_0(z) = f(0,0)z^0 + $( Rest alles 0 ) = 1
Wie zu erwarten bleibt die Rekursion nach n.
Ich hab das jetzt genauso versucht:
$F_n(z)\zeta^k = \frac{z}{1-z^n}F_{n-1}(z)\zeta^k = \frac{z\zeta}{1-z^n}F_{n-1}(z)\zeta^{k-1} \Leftrightarrow $
$G(\zeta) = \sum_{n=0}^\infty{F_n \zeta^n =\sum_{n=0}^\infty{\frac{z\zeta}{1-z^n}F_{n-1}\zeta^{n-1} = \zeta \sum_{n=1}^\infty{\frac{z}{1-z^n}F_{n-1}\zeta^{n-1}$
$= \zeta \sum_{n=0}^\infty{\frac{z}{1-z^{n+1}}F_{n}\zeta^{n} $
Jetzt habe ich ein n in der Summe, und weiß nicht weiter.
hab ich da nen Denkfehler, oder geht so was vieleicht ganz anders.
Vielen Dank an alle, die sich dazu Gedanken machen.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt
![[]](/images/popup.gif) andresForum
:
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Do 26.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
