Rekursive Formel zu expliziter Darstellung

27.06.2019, 16:00

Moesen

Rekursive Formel zu expliziter Darstellung

Hallo,
ich schreibe gerade meine Bachelor Abschlussarbeit für mein Informatikstudium. Dabei geht es momentan um die Abbildung
$\begin{eqnarray*} f: \mathbb{Z} \rightarrow\mathbb{Z}, n \mapsto q(n,n) \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} q: \mathbb{Z} \times \mathbb{Z} \rightarrow\mathbb{Z} \end{eqnarray*}$ folgendermaßen rekursiv definiert:
$\begin{eqnarray*} q(a,b)=\left\{\begin{array}{ll} 0, & a<1 \lor b<1 \\ 1, & a=1 \lor b=1\\ q(a-b,b)+q(a,b-1)+1, & sonst\end{array}\right. . \end{eqnarray*}$
(Interessant sind offensichtlich nur Werte größer als 2)

Nun ist die Frage wie ich für $\begin{eqnarray*} f(n)=q(n,n) = ... \end{eqnarray*}$ eine nicht Rekursive Darstellung errechnen kann. Also frage ich konkret nach Methoden oder publizierten Arbeiten oder Ideen die mir helfen könnten.

Jetzt schon mal vielen dank

Moesen

27.06.2019, 16:04

HAL 9000

Auf diesen Beitrag antworten »

RE: Rekusrive Formel zu expliziter

Zitat:

Original von Moesen
Dabei ist $\begin{eqnarray*} q: \mathbb{Z} \times \mathbb{Z} \rightarrow\mathbb{Z} \end{eqnarray*}$ folgendermaßen rekursiv definiert:
$\begin{eqnarray*} q(a,b)=\left\{\begin{array}{ll} 0, & a<1 \lor b<1 \\ 1, & a=1 \lor b=1\\ q(a-b,b)+q(a,b-1)+1, & sonst\end{array}\right. . \end{eqnarray*}$

Irgendwie ist hier bereits ein Logikfehler in der Funktionsdefinition: Nach der ist sowohl q(1,0)=0 (erste Zeile) als auch q(1,0)=1 (zweite Zeile). unglücklich

Sieht also so aus, als hast du dich irgendwo verschrieben.

Womöglich meinst du in der zweiten Zeile auch "exklusive erste Zeile", d.h., $\begin{eqnarray*} (a\geq 1)\wedge (b\geq 1)\wedge ((a=1)\vee (b=1)) \end{eqnarray*}$ , aber es steht eben nicht da.

27.06.2019, 16:12

Moesen

Auf diesen Beitrag antworten »

Mein Fehler,
so müsste es sein:
$\begin{eqnarray*} p(a,b)=\left\{\begin{array}{ll} 0, & a<1 \lor b<1 \\ 1, & (a=1 \land b \geq 1)\lor (a \geq 1 \land b=1)\\ p(a-b,b)+p(a,b-1)+1, & sonst\end{array}\right. . \end{eqnarray*}$

27.06.2019, 16:56

HAL 9000

Auf diesen Beitrag antworten »

Irgendwie erinnert mich die Rekursion an die der Partitionsfunktion $\begin{eqnarray*} P(n,k) \end{eqnarray*}$ für Summe $\begin{eqnarray*} n \end{eqnarray*}$ bei fester Summandenanzahl $\begin{eqnarray*} k \end{eqnarray*}$ , die lautet dort nämlich

$\begin{eqnarray*} P(n,k) = P(n-k,k) + P(n-1,k-1) \end{eqnarray*}$ .

Kann dir aber auf die Schnelle nicht sagen, ob das was nützt: Zum einen kenne ich auch keine explizite Darstellung von $\begin{eqnarray*} P \end{eqnarray*}$ , zum anderen ist die Rekursion ja auch ein bisschen anders. Ist halt nur ein bisschen Brainstorming.

22.07.2019, 17:21

Moesen

Auf diesen Beitrag antworten »

Für jeden der dieses Thema nochmal mit Google findet oder einfach nur Interesse hat:

Ich konnte tatsächlich meine Funktion $\begin{eqnarray*} f(n) \end{eqnarray*}$ über die Rekursionsformel $\begin{eqnarray*} P(n,k)=P(n-k,k)+P(n-1,k-1) \end{eqnarray*}$ (für Summe $\begin{eqnarray*} n \end{eqnarray*}$ bei fester Summandenanzahl $\begin{eqnarray*} k \end{eqnarray*}$ ) und einer entsprechenden Formel für eine Maximalgröße der einzelnen Summanden abschätzen.

Somit kam ich auf $\begin{eqnarray*} f(n) \leq 2*P(n) \end{eqnarray*}$ , wobei $\begin{eqnarray*} P(n) \end{eqnarray*}$ die normale Partitionsfunktion bezeichnet.

Mit der asymptotischen Formel von Godfrey Harold Hardy und S. Ramanujan gillt also in O-Notation:
$\begin{eqnarray*} f(n) = \mathcal{O}(\frac{e^{\pi * \sqrt{\frac{2n}{3} } }}{n} ) \end{eqnarray*}$

22.07.2019, 17:30

HAL 9000

Auf diesen Beitrag antworten »

Freut mich, dass mein Brainstorming dann doch nicht ganz unnütz war. Augenzwinkern

Neue Frage »

Antworten »

Rekursive Formel zu expliziter Darstellung

Verwandte Themen