"verschränktes Rekursionsgleichungssystem"

23/04/2008 - 09:02 von Robert Hartmann | Report spam
Hallo zusammen,


Ich habe einige Probleme ein, ich nenne es mal,
"verschrànktes Rekursionsgleichungssystem"
in eine geschlossene Formel umzuwandeln -
getreu dem Motto "rekursiv geht hàufig schief".

Wie ich mit "normalen" Rekursionsgleichungen
um zugehen habe, das weiß ich schon:

http://home.tu-clausthal.de/~ifrh/inf1-ws2006-07_zusatzmaterial-rekursionsgleichungen.pdf
(Wenn jemand dort noch Fehler findet,
bin ich um jeden Hinweis dankbar :-) )

Nun zu dem rekursiven Gleichungssystem:

n >= 7 ist eine feste aber sonst frei gewàhlte natürliche Zahl,
g eine beliebige natürliche Zahl.


v(g,n) = b(g,n) + r(g,n)

b(0,n) = 1
b(1,n) = n
b(g,n) = (n-5)*b(g-1,n) + (n-6)*r(g-1,n)


r(0,n) = 0
r(1,n) = 0
r(g,n) = b(g-1,n) + r(g-1,n)


Ich suche eine geschlossene Formel für v(g,n).

Kennt jemand den Weg diese Art der verschrànkten
Rekursion aufzulösen?

Meine Internet-Suche und das Stöbern in der
Unibibliothek hat irgendwie nichts gebracht.

Besten Gruß,
Robert
 

Lesen sie die antworten

#1 Jannick Asmus
23/04/2008 - 09:20 | Warnen spam
On 23.04.2008 09:02, Robert Hartmann wrote:
Hallo zusammen,


Ich habe einige Probleme ein, ich nenne es mal,
"verschrànktes Rekursionsgleichungssystem"
in eine geschlossene Formel umzuwandeln -
getreu dem Motto "rekursiv geht hàufig schief".

Wie ich mit "normalen" Rekursionsgleichungen
um zugehen habe, das weiß ich schon:

http://home.tu-clausthal.de/~ifrh/inf1-ws2006-07_zusatzmaterial-rekursionsgleichungen.pdf

(Wenn jemand dort noch Fehler findet,
bin ich um jeden Hinweis dankbar :-) )

Nun zu dem rekursiven Gleichungssystem:

n >= 7 ist eine feste aber sonst frei gewàhlte natürliche Zahl,
g eine beliebige natürliche Zahl.


v(g,n) = b(g,n) + r(g,n)

b(0,n) = 1
b(1,n) = n
b(g,n) = (n-5)*b(g-1,n) + (n-6)*r(g-1,n)


r(0,n) = 0
r(1,n) = 0
r(g,n) = b(g-1,n) + r(g-1,n)


Ich suche eine geschlossene Formel für v(g,n).

Kennt jemand den Weg diese Art der verschrànkten
Rekursion aufzulösen?



Entkopple die Gleichungen, indem Du für (b,r) eine rekursive
Matrixgleichung aufstellst und diese diagonalisierst (habe gecheckt,
dass diese tatsàchlich diagonalisierbar ist - hoffe, ich habe mich nicht
vertan). Die entkoppelte Diagonalversion kannst Du dann nach den
bekannten Methoden lösen - und nach Rücktransformation hast Du das Ergebnis.

Meine Internet-Suche und das Stöbern in der
Unibibliothek hat irgendwie nichts gebracht.

Besten Gruß,
Robert



HTH.


Best wishes,
Best wishes,
J.

Ähnliche fragen