Rekursionsgleichung aufstellen

26.05.2016, 17:00

Shizmo

Rekursionsgleichung aufstellen

Hallo, ich soll eine Rekursion aufstellen, weiß aber nicht wie ich das angehen soll.

Die Angabe ist im Anhang und meine Idee für 2x3 Bretter auch,
generell weiß ich dann:
$\begin{eqnarray*} M(0)=1 \end{eqnarray*}$
$\begin{eqnarray*} M(1)=1 \end{eqnarray*}$
$\begin{eqnarray*} M(2)=2 \end{eqnarray*}$
$\begin{eqnarray*} M(3)=7 \end{eqnarray*}$
$\begin{eqnarray*} M(4)=33 \end{eqnarray*}$ (laut Angabe)

Die Startwerte werden aufjedenfall M(0) und M(1) sein, eventuell aber auch M(2).

Aber wie komme ich jetzt auf eine Rekurrenzgleichung??

LG

26.05.2016, 18:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Shizmo
$\begin{eqnarray*} M(2)=2 \end{eqnarray*}$
$\begin{eqnarray*} M(3)=7 \end{eqnarray*}$

Da bin ich anderer Meinung:
$\begin{eqnarray*} M(2)=5 \end{eqnarray*}$
$\begin{eqnarray*} M(3)=11 \end{eqnarray*}$

Das liegt vermutlich daran, dass du Varianten, die durch Drehung/Spiegelung ineinander übergehen, als gleich ansiehst - solltest du nicht tun, denn so ist das hier nicht gemeint.

EDIT: Hab mir jetzt erst deine Skizze angeschaut: Dreh einfach mal die vier Blöcke mit genau einem roten L um 180°, dann hast du die vier fehlenden Varianten. Augenzwinkern

26.05.2016, 22:13

Shizmo

Auf diesen Beitrag antworten »

Danke für deine Antwort HAL 9000

Hmm okay, hatte das vorher auch schon mal gedacht, hab mich dann aber doch umentschieden Hammer

Aber wie stell ich nun eine Rekursionsgleichung auf, durch rum probieren und raten oder gibts da irgendwelche Tricks, Algorithmen??

Mein neuester Versuch wäre irgendwas in der Richtung:
$\begin{eqnarray*} M(n) = 2\cdot M(n-1)+2\cdot M(n-2) +1 \end{eqnarray*}$
Passt bis M(4) außer für M(3) Big Laugh

Oh man...

26.05.2016, 22:41

HAL 9000

Auf diesen Beitrag antworten »

Ich komme auf $\begin{align*} M(n) = M(n-1) + 4\cdot M(n-2) + 2\cdot M(n-3) \end{align*}$ , was sich gut begründen lässt, wenn man genau wie im obigen Hinweis beschrieben vorgeht.

26.05.2016, 22:48

Shizmo

Auf diesen Beitrag antworten »

Wow ich bin beeindruckt Freude

Aber wie du darauf genau gekommen bist ist mir ein Rätsel verwirrt

Ich denke du meinst den Hinweis mit dem linken Rand? Könntest du mir das vllt etwas genauer erklären wie du darauf gekommen bist??

26.05.2016, 23:00

HAL 9000

Auf diesen Beitrag antworten »

Systematisch die Fälle betrachten, die am linken Rand möglich sind - das ist keine Zauberei oder tolle "Eingebung", sondern geduldige sorgfältige Arbeit. Ich bezeichne mit E das 1x1-Element, mit L das L-förmige Element.

Fall 1: Eine Spalte bestehend aus zwei E übereinander, rechts davon als Rest ein Block $\begin{align*} 2\times (n-1) \end{align*}$ , macht $\begin{align*} M(n-1) \end{align*}$ Möglichkeiten.

Fall 2: Eine Spalte bestehend aus einem E, sowie 1/3 von L. Dann ist die zweite Spalte der Rest des L, rechts davon ein Block $\begin{align*} 2\times (n-2) \end{align*}$ , macht $\begin{align*} 2\cdot M(n-2) \end{align*}$ Möglichkeiten (das E ganz links kann oben oder unten stehen!).

Fall 3: Die ganz linke Spalte besteht aus 2/3 eines L, das restliche 1/3 des L liegt in der zweiten Spalte (oben oder unten). Was den Rest der zweiten Spalte betrifft, gibt es zwei Unterfälle:

Fall 3.1: Ein E, rechts davon ein Block $\begin{align*} 2\times (n-2) \end{align*}$ , macht wieder $\begin{align*} 2\cdot M(n-2) \end{align*}$ Möglichkeiten, wie in Fall 2.

Fall 3.2: 1/3 eines zweiten L, die dritte Spalte enthält die restlichen 2/3 dieses L, rechts davon ein Block $\begin{align*} 2\times (n-3) \end{align*}$ , macht $\begin{align*} 2\cdot M(n-3) \end{align*}$ Möglichkeiten.

Das ist alles, mehr Möglichkeiten gibt es nicht. Alles aufsummiert ergibt die obige Rekursionsgleichung.

26.05.2016, 23:33

Shizmo

Auf diesen Beitrag antworten »

Wow Danke!!! Das ist mal eine tolle Erklärung!!! Du hilfst mir wirklich sehr.

Ich werde es morgen nochmal alles in Ruhe durchgehen, falls noch eine Frage auftaucht meld ich mich nochmal.

Vielen Dank!!! Freude

27.05.2016, 08:44

Huggy

Auf diesen Beitrag antworten »

Die Randbetrachtung von HAL kann man noch etwas anders aufziehen. Um das Brett zu füllen, müssen die elementaren Bausteine E und L in bestimmter Weise zu Kombibausteinen zusammengesetzt werden:

I bestehend aus 2 übereinanderliegen E.
Q ein 2X2-Quadrat bestehend aus einem L und einem E. Es gibt 4 Varianten.
R ein 3x2-Rechteck bestehend aus 2 verschränkten L. Es gibt 2 Varianten.

Der Rand muss aus einem dieser 3 Kombibausteine bestehen. Das ergibt wieder die von HAL genannte Rekursionsgleichung.

27.05.2016, 09:07

HAL 9000

Auf diesen Beitrag antworten »

Genau. In der Darstellung oben wollte ich nur sorgfältig Spalte für Spalte vorgehen, weil man in dieser Systematik besser erkennt, dass keine Möglichkeit ausgelassen wird UND auch keine Variante doppelt gezählt wird. Da muss man dann eben in Kauf nehmen, dass die "eigentlich gleichen" Fälle 2 und 3.1 in der Hierarchie an unterschiedlichen Positionen auftauchen. Augenzwinkern

28.05.2016, 19:20

Shizmo

Auf diesen Beitrag antworten »

Bin grad nochmal alles durchgegangen und hab es verstanden.

Vielen Dank nochmal, ihr habt mir wirklich sehr geholfen!!!!

27.08.2021, 22:48

sonny1001

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Die Randbetrachtung von HAL kann man noch etwas anders aufziehen. Um das Brett zu füllen, müssen die elementaren Bausteine E und L in bestimmter Weise zu Kombibausteinen zusammengesetzt werden:

I bestehend aus 2 übereinanderliegen E.
Q ein 2X2-Quadrat bestehend aus einem L und einem E. Es gibt 4 Varianten.
R ein 3x2-Rechteck bestehend aus 2 verschränkten L. Es gibt 2 Varianten.

Der Rand muss aus einem dieser 3 Kombibausteine bestehen. Das ergibt wieder die von HAL genannte Rekursionsgleichung.

Woher weiß man, des z.B. nicht noch ein 4x2 Rechteck gibt?

27.08.2021, 23:02

HAL 9000

Auf diesen Beitrag antworten »

Welches 4x2-Rechteck (d.h. mit welcher Aufteilung in E und L-Stücke) soll denn deiner Meinung nach der obigen Fallunterscheidung entwischt sein? verwirrt

28.08.2021, 11:13

Leopold

Auf diesen Beitrag antworten »

Man kann die Rekursion um eine Stufe reduzieren. Betrachtet man nämlich die Folge der $\begin{align*} L(n) \end{align*}$ mit

$\begin{align*} \begin{cases} L(0) = 1, \ L(1) = 1 & \\ L(n) = 2 \left( \, L(n-1) + L(n-2) \, \right) + (-1)^n , \ n \geq 2 \end{cases} \end{align*}$

so berechnet man damit zunächst

$\begin{align*} L(2) = 2 \cdot \left( 1 + 1 \right) + (-1)^2 = 5 \end{align*}$

und wendet in der folgenden Gleichung beim zweiten Summanden der rechten Seite erneut die Rekursionsvorschrift an:

$\begin{align*} L(n) = L(n-1) + L(n-1) + 2L(n-2) + (-1)^n \end{align*}$

$\begin{align*} = L(n-1) + 2L(n-2) + 2L(n-3) + (-1)^{n-1} + 2L(n-2) + (-1)^n \end{align*}$

$\begin{align*} = L(n-1) + 4L(n-2) + 2L(n-3) \end{align*}$

Die $\begin{align*} L(n) \end{align*}$ und die $\begin{align*} M(n) \end{align*}$ haben dieselben drei Startwerte und genügen derselben Rekursionsvorschrift und müssen folglich übereinstimmen. Anders gesagt:

$\begin{align*} M(n) = 2 \left( \, M(n-1) + M(n-2) \, \right) + (-1)^n \, , \ \ n \geq 2 \end{align*}$

Aus Spaß an der Freud habe ich einmal HALs Rekursion in eine explizite Form umgewandelt:

$\begin{align*} M(n) = (-1)^n + \frac{\sqrt{3}}{3} \left( \left( 1 + \sqrt{3} \right)^n - \left( 1 - \sqrt{3} \right)^n \right) \, , \ \ n \geq 0 \end{align*}$

Die $\begin{align*} M(n) \end{align*}$ sind der rekursiven Definition nach natürliche Zahlen. Da der Ausdruck $\begin{align*} \frac{\sqrt{3}}{3} \left( 1 - \sqrt{3} \right)^n \end{align*}$ dem Betrage nach streng monoton fallend gegen 0 konvergiert, kann man ihn, sobald sein Betrag $\begin{align*} < \frac{1}{2} \end{align*}$ wird, weglassen und zur nächsten ganzen Zahl runden. Man findet so:

$\begin{align*} M(n) = (-1)^n + \left \lfloor \frac{\sqrt{3}}{3} \left( 1 + \sqrt{3} \right)^n + \frac{1}{2} \right \rfloor \, , \ \ n \geq 1 \end{align*}$

Wer es lieber ohne Wurzeln mag, kann auch unter Inkaufnahme eines Summenzeichens Folgendes nehmen:

$\begin{align*} M(n) = (-1)^n + 2 \sum_{0 \leq k < \frac{n}{2}} {n \choose {2k+1}} 3^k \, , \ \ n \geq 0 \end{align*}$

Das bekommt man aus der Formel oben mit Hilfe des binomischen Lehrsatzes.

Man kennt diese ganzen Geschichten von den Fibonacci-Zahlen.

28.08.2021, 12:27

sonny1001

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Welches 4x2-Rechteck (d.h. mit welcher Aufteilung in E und L-Stücke) soll denn deiner Meinung nach der obigen Fallunterscheidung entwischt sein? verwirrt

Mir geht es darum, zu erkennen, wann ich keine größeren Rechtecke mehr zu betrachten brauche.

28.08.2021, 12:37

sonny1001

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Systematisch die Fälle betrachten, die am linken Rand möglich sind - das ist keine Zauberei oder tolle "Eingebung", sondern geduldige sorgfältige Arbeit. Ich bezeichne mit E das 1x1-Element, mit L das L-förmige Element.

Fall 1: Eine Spalte bestehend aus zwei E übereinander, rechts davon als Rest ein Block $\begin{align*} 2\times (n-1) \end{align*}$ , macht $\begin{align*} M(n-1) \end{align*}$ Möglichkeiten.

Fall 2: Eine Spalte bestehend aus einem E, sowie 1/3 von L. Dann ist die zweite Spalte der Rest des L, rechts davon ein Block $\begin{align*} 2\times (n-2) \end{align*}$ , macht $\begin{align*} 2\cdot M(n-2) \end{align*}$ Möglichkeiten (das E ganz links kann oben oder unten stehen!).

Fall 3: Die ganz linke Spalte besteht aus 2/3 eines L, das restliche 1/3 des L liegt in der zweiten Spalte (oben oder unten). Was den Rest der zweiten Spalte betrifft, gibt es zwei Unterfälle:

Fall 3.1: Ein E, rechts davon ein Block $\begin{align*} 2\times (n-2) \end{align*}$ , macht wieder $\begin{align*} 2\cdot M(n-2) \end{align*}$ Möglichkeiten, wie in Fall 2.

Fall 3.2: 1/3 eines zweiten L, die dritte Spalte enthält die restlichen 2/3 dieses L, rechts davon ein Block $\begin{align*} 2\times (n-3) \end{align*}$ , macht $\begin{align*} 2\cdot M(n-3) \end{align*}$ Möglichkeiten.

Das ist alles, mehr Möglichkeiten gibt es nicht. Alles aufsummiert ergibt die obige Rekursionsgleichung.

Kann man diese Lösungsidee immer anwenden?
Ich denke da an das Turm-Problem aus Peter Tittmann S.78. Da kommt er auf zwei Rekurrenzgleichungen, die gekoppelt sind. Wenn ich sie entkopple lauten sie:
$\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$
Was auch auf das richtige Ergebnis b(6)=1681 führt. Nur kann ich mir diese Rekurrenzgleichung nicht plausibel machen.

28.08.2021, 13:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Man kann die Rekursion um eine Stufe reduzieren.

Nun, du wandelst eine homogene lineare Differenzengleichung dritter Ordnung in eine inhomogene lineare Differenzengleichung zweiter Ordnung um. Wäre natürlich noch schön, wenn man eine direkte inhaltliche Begründung von letzterer angeben könnte. Augenzwinkern

Was das Finden einer expliziten Darstellung von ersterer betrifft, dann kann man streng der Lösungstheorie folgen: Die zugehörige charakteristische Gleichung ist

$\begin{eqnarray*} 0 = \lambda^3-\lambda^2-4\lambda-2 = \left(\lambda+1\right)\left(\lambda^2-2\lambda-2\right) \end{eqnarray*}$

mit den drei Lösungen $\begin{eqnarray*} \lambda_1 = -1,\lambda_{2,3}=1\pm\sqrt{3} \end{eqnarray*}$ , dann entsprechendem Lösungsansatz $\begin{eqnarray*} M(n) = C_1 \lambda_1^n + C_2 \lambda_2^n + C_3 \lambda_3^n \end{eqnarray*}$ und Gewinnung der drei Koeffizienten $\begin{eqnarray*} C_1,C_2,C_3 \end{eqnarray*}$ aus drei Anfangswerten.

Zitat:

Original von sonny1001
Mir geht es darum, zu erkennen, wann ich keine größeren Rechtecke mehr zu betrachten brauche.

M.E. ist die Vollständigkeit der Fallunterscheidung ausreichend klar erläutert - im Rahmen dieser Betrachtungen besteht schlicht keine Notwendigkeit mehr, auch noch die vierte Spalte zu betrachten: Man "erfindet" doch keine weiteren Fälle, wenn man bereits alle Möglichkeiten erfasst hat!

Wenn du so darauf pochst, dass dir das nicht reicht und diesen Verdacht/Unmut aber gleichzeitig nicht weiter erläuterst, dann weiß ich auch nicht, wie ich dir helfen kann. unglücklich

Zitat:

Original von sonny1001
Ich denke da an das Turm-Problem aus Peter Tittmann S.78.

Da ich das nicht kenne und nun auch nicht gleich losrenne, mir das Buch (?) zu besorgen, kann ich nichts dazu sagen. Augenzwinkern

EDIT: Ok, durch den Beitrag von Huggy sehe ich jetzt, dass es wohl um dieses Problem geht. War mir nicht bewusst, dass du das hier schon als Threadthema gestartet hattest.

Neue Frage »

Antworten »

Rekursionsgleichung aufstellen

Verwandte Themen