Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Von expliziter Formel auf Rekursive Formel

Von expliziter Formel auf Rekursive Formel

Universität / Fachhochschule

Tags: binär, Folge, Rekursionsformel, rekursiv

Nicoostendorf aktiv_icon

15:15 Uhr, 22.11.2018

Hallo,
Ich soll für die Anzahl an binären Such Bäumen mit

n

Schlüsseln eine rekursive Formel finden.

Ich habe die explizite Formel bereits herausgefunden die wäre:

b_{n} = \frac{1}{n + 1} \cdot (2 n

über

n)

Also:

N = 1 : 1

N = 2 : 2

N = 3 : 5

N = 4 : 14

N = 5 : 42

N = 6 : 132

Kann mir jetzt jemand erklären wie ich von diesem Wissen zur rekursiven Funktion komme?

MfG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Mitternachtsformel

Edddi aktiv_icon

15:31 Uhr, 22.11.2018

b_{n} = \frac{1}{n + 1} (\begin{matrix} 2 n \\ n \end{matrix})

b_{n - 1} = \frac{1}{n} (\begin{matrix} 2 n - 2 \\ n - 1 \end{matrix}) = \frac{n}{(2 n - 1) (2 n)} (\begin{matrix} 2 n \\ n \end{matrix})

. .

. hilft dir das weiter?

;-)

Nicoostendorf aktiv_icon

15:44 Uhr, 22.11.2018

Muss ich jetzt bestimmen, wie ich von der Formel

n - 1

auf die Formel

n

komme?

Edddi aktiv_icon

15:47 Uhr, 22.11.2018

. .

. du musst doch nur

b_{n - 1} = \frac{n}{(2 n - 1) (2 n)} (\begin{matrix} 2 n \\ n \end{matrix})

nach

(\begin{matrix} 2 n \\ n \end{matrix}) = ...

. umstellen und dies dann in

b_{n} = \frac{1}{n + 1} (\begin{matrix} 2 n \\ n \end{matrix})

einsetzen, dann hast du

b_{n} = f (b_{n - 1})

;-)

Nicoostendorf aktiv_icon

16:16 Uhr, 22.11.2018

Irgendwie stehe ich absolut auf dem Schlauch..
Ich hab es umgeformt und dann für

(2 n

über

n)

in die Formel von

b_{n}

eingesetzt. Jedoch ergibt die Lösung, wenn ich die dann vorhandene rekursive Formel nutze keinen Sinn...

Tut mir leid, falls ich mich extrem dumm anstelle, aber die letzte Vorlesung mit soetwas ist bei mir schon länger her..

Roman-22

17:05 Uhr, 22.11.2018

>

einsetzen, dann hast du bn=f(bn−1)
Da sollte, so wie ich eine rekursive Definition verstehe, aber keine Abhängigkeit vom Index

n

mehr auftreten und diese Bedingung scheint bei deinem Vorschlag nicht gegeben zu sein, oder?

Edddi aktiv_icon

19:35 Uhr, 22.11.2018

. .

. au Mist, das hab ich mir wohl zu leicht gemacht. Ich denk nochmal drüber nach.

;-)

Edddi aktiv_icon

20:17 Uhr, 22.11.2018

. .

. das ist für heut Abend starker Tobak.

Vielleicht hilft dir das hier weiter:

de.wikipedia.org/wiki/Catalan-Zahl

Wie der Her Segner auf die Rekursionsformel gekommen ist, weiß ich nicht. Es wäre dann:

b_{n + 1} = \sum_{k = 0}^{n} b_{k} b_{n - k}

Somit mit

b_{0} = 1

b_{1} = \sum_{k = 0}^{0} b_{k} b_{n - k} = b_{0} b_{0} = 1 \cdot 1 = 1

b_{2} = \sum_{k = 0}^{1} b_{k} b_{n - k} = b_{0} b_{1} + b_{1} b_{0} = 1 \cdot 1 + 1 \cdot 1 = 2

b_{3} = \sum_{k = 0}^{2} b_{k} b_{n - k} = b_{0} b_{2} + b_{1} b_{1} + b_{2} b_{0} = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5

usw.

;-)

Roman-22

20:33 Uhr, 22.11.2018

Es handelt sich hier um die sog. Catalan-Zahlen.
Zwei mögliche Rekursionsformeln (die allerdings auch nicht völlig vom Index

n

unabhängig sind) bietet Tante Wiki an
de.wikipedia.org/wiki/Catalan-Zahl

An sich sollte man genügend Literatur darüber finden.

EDIT: Oops, zu spät. hatte den Thread wohl zu lange offen gelassen und das Autoupdate funktioniert dann ja leider nicht mehr.

Nicoostendorf aktiv_icon

14:55 Uhr, 26.11.2018

Danke euch zweien nochmal, verstehe zwar nicht ganz wie man zu der Formel gelangt, aber da solche Aufgaben nur ein Exkurs waren ist es nicht so wild! Catalan Zahlen sind mir bekannt gewesen, jedoch hab ich das irgendwie nicht damit verbunden..

Danke!

1449365

1448585

	Status: nicht eingeloggt	Noch nicht registriert?