Aufgabe H10.2.6
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Asymptotisches Verhalten Catalan-Folge
Aufgabe 5)
CATALAN-Zahlen:
b(0) = 1
b(n+1) = sum[ b(i) b(j) | i+j=n]
Aufgabe 6) Wie verhält sich l(n) asymtotisch? Begründen Sie ihre Antwort!
Äh, wie? Also folgendes weiß ich auswendig:
b(n) = 1/(n+1) ((2n, n))
((n,k)) soll der Binomialkoffizient n über k sein
Da ist ja wohl nicht ernsthaft die Herleitung dieser Formel erwartet (aus P-Rekursion)?! Uff…
Mit Stirling ( n! = (n/e)^n sqrt(2 pi n) + O(1/n) ) kann man dann leicht
b(n) in O(4^n/sqrt(pi n^3))
herleiten. (so stehts im skript).
Wobei ich mich frage was das Pi in der Wurzel verloren hat? Das ist schließlich ein konstanter Faktor:
4^n/sqrt(pi n^3) = 4^n / (sqrt(pi)*sqrt(n^3)) = 1/(sqrt(pi) * 4^n/sqrt(n^3)
Warum wird es dann nicht weggelassen? Die zwei läßt man ja auch weg… ?