Rekurrenzgleichung für "L"-Turm

29.08.2021, 14:14

sonny1001

Rekurrenzgleichung für "L"-Turm

Ich möchte mein Verständnis für das Aufstellen für Rekurrenzgleichungen festigen. Ich habe dazu die Turm-Aufgabe etwas abgeändert und möchte Euch bitten, meine Argumentation zu überprüfen.
Im wesentlichen verwende ich die Argumentation von huggy aus einem anderen thread.

Hier die Aufgabe:
Wir haben einen ausreichend großen Vorrat an Holzbausteinen vom Format eines "L" (Platte 2x2x1 mit ausgeschnittenem Würfel 1x1x1). Auf wieviel verschiedene Arten können wir einen Turm der Höhe n mit einer Grundfläche der Größe 2 x2 bauen?

Lösung:
1.Fall
1 liegendes und 1 stehendes L darauf 2 parallel stehende L Höhe k=3, Möglichkeiten 8

2.Fall
2 parallel stehende L darauf 2 parallel stehende L Höhe k=3, Möglichkeiten 4

3.Fall
2 antiparallel stehende L darauf 2 antiparallel stehende L Höhe k=3, Möglichkeiten 4

$\begin{eqnarray*} b(n)=16\sum_{k=3}^{n} b(n-k)\\ b(n)=16\sum_{k=0}^{n-3} b(k)\\ b(n+1)=16\sum_{k=0}^{n-2} b(k)\\ b(n+1)-b(n)=16b(n-2)\\ b(n+1)=b(n)+16b(n-2)\\ b(n)=b(n-1)+16b(n-3)\\ mit \\b_0=1; b_1=1; b_2=1 (kein Turm dieser Höhe, daher jeweils 1) \end{eqnarray*}$

29.08.2021, 14:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sonny1001
(kein Turm dieser Höhe, daher jeweils 1)

Türme der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ sind unmöglich, wenn $\begin{eqnarray*} n \end{eqnarray*}$ nicht durch 3 teilbar ist. Daher gilt für diese $\begin{eqnarray*} n \end{eqnarray*}$ dann logischerweise $\begin{eqnarray*} b(n)=0 \end{eqnarray*}$ statt 1. unglücklich

-----------------------------------------------------------------

Möglicher Zugang zum Problem (nicht sehr effektiv, führt aber mit Geduld zum Ziel): Es seien $\begin{eqnarray*} b(n),c(c),d(n),e(n),f(n) \end{eqnarray*}$ die Anzahl der Türme der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ , deren Grundschicht folgendermaßen vorbelegt ist:

code:
1: 2:	o o o o o o o x x o o o x o x x x o x x

(o steht für leer und x für vorbelegt)

Dann kann man eine Reihe von verzahnten Rekursionsgleichungen aufstellen, als erste etwa

$\begin{eqnarray*} b(n) = 4f(n)+4d(n-1)+4e(n-1) \end{eqnarray*}$ .

EDIT: Hab mal nachträglich meine Bezeichnungen so angepasst, dass $\begin{eqnarray*} b(n) \end{eqnarray*}$ bei uns beiden inhaltlich dieselbe Bedeutung hat.

29.08.2021, 14:55

sonny1001

Auf diesen Beitrag antworten »

Ist meine Rekurrenzgleichung falsch?

29.08.2021, 14:58

HAL 9000

Auf diesen Beitrag antworten »

Mit einem kurzen Blick drauf stelle ich fest, dass bei dir $\begin{eqnarray*} b(n)\neq 0 \end{eqnarray*}$ auch für nicht durch 3 teilbare $\begin{eqnarray*} n \end{eqnarray*}$ möglich ist (selbst wenn du deine Anfangswerte korrigierst). Damit muss das falsch sein.

Es ist übrigens $\begin{eqnarray*} b(1)=0,b(2)=0,b(3)=44 \end{eqnarray*}$ - zähle also mal richtig nach.

-------------------------------------------------------------------------------

Ich hab mal das komplette Paket an Rekursionen aufgestellt:

$\begin{eqnarray*} b(n) = 4f(n)+4d(n-1)+4e(n-1) \end{eqnarray*}$ .
$\begin{eqnarray*} c(n) = b(n-1)+6f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} d(n) = 2c(n-1)+b(n-2) \end{eqnarray*}$
$\begin{eqnarray*} e(n) = 2b(n-2) \end{eqnarray*}$
$\begin{eqnarray*} f(n) = 2d(n-1) \end{eqnarray*}$

Wenn ich mich nicht verrechnet habe, ergibt das aufgedröselt hin zu $\begin{eqnarray*} b(n) \end{eqnarray*}$ die Rekursion $\begin{eqnarray*} b(n) = 68b(n-3) - 192b(n-6) \end{eqnarray*}$ mit den Startwerten $\begin{eqnarray*} b(0)=1 \end{eqnarray*}$ und $\begin{eqnarray*} b(3)=44 \end{eqnarray*}$ .

Eine explizite Darstellung ist $\begin{eqnarray*} b(3k) = \frac{\left(\sqrt{241}+5\right)\cdot \left(34+2\sqrt{241}\right)^k+\left(\sqrt{241}-5\right)\cdot \left(34-2\sqrt{241}\right)^k}{2\sqrt{241}} \end{eqnarray*}$ .

30.08.2021, 10:55

sonny1001

Auf diesen Beitrag antworten »

Ich versuche einmal, die Vorgehensweise nachzuvollziehen und bitte um eure Überprüfung:
- ich überlege mir alle Vorbelegungen die möglich sind ohne Berücksichtigung von Drehungen und Spiegelungen. Das sind 5 Stück.
- Ich nehme mir eine Vorbelegung heraus, die ich auf die linke Seite der Gleichung schreibe. Also muss ich 5 Gleichungen aufstellen.
- ich überlege mir, wie ich mit möglichst wenigen Steinen auf eine andere Vorbelegung komme. Die Anzahl der Variationen, um auf diese Vorbelegung zu kommen, gibt den Vorfaktor in der Gleichung.
- Die Anzahl der dabei entstehenden geschlossenen Schichten, verringert die Höhe des daraufgesetzten Turmes um die gleiche Höhe.
Damit begründe ich jetzt die Gleichungen.
f(n)=2d(n-1) : 1 senkrecht stehendes L kann an Turmdiagonalen gespiegelt werden (2 Möglichkeiten) , eine geschlossene Schicht.
e(n)= 2b(n-2) : 2 senkrecht stehende L kann an Turmdiagonalen gespiegelt werden (2 Möglichkeiten) , zwei geschlossene Schichten
d(n)=2c(n-1)+b(n-2): 1 senkrecht stehendes L kann gespiegelt werden (2 Möglichkeiten) , eine geschlossene Schicht. + 2 parallele senkrecht stehende L , zwei geschlossene Schichten.
c(n)=b(n-1)+6f(n-1): 1liegendes L, eine geschlossene Schicht. + 1 senkrecht stehendes L und ein liegendes L , eine geschlossene Schicht. 4 Drehungen, 2Spiegelungen
b(n)=4f(n)+4d(n-1)+4e(n-1): 1 liegendes L , 4Drehungen ,keine geschlossene Schicht. + 2 parallel senkrecht stehende L , 4 Drehungen , eine geschlossene Schicht. + 2 antiparallel senkrecht stehendes L , 2 Drehungen und 2 Spiegelungen, eine geschlossene Schicht.

30.08.2021, 11:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sonny1001
- ich überlege mir, wie ich mit möglichst wenigen Steinen auf eine andere Vorbelegung komme.

Nein, das ist nicht der Grundgedanke:

Es sind ALLE Varianten zu betrachten, mit denen
- eine andere Belegung der Grundschicht erreicht werden kann, ohne das L-Stücke in die nächste Schicht ragen, das betrifft nur b
- sofern L-Stücke in die nächste Schicht ragen, auch die 2x2-Grundschicht komplettiert werden kann, das betrifft alle Fälle.
Dabei werden aber auch wirklich nur soviel L-Stücke verbaut, wie für dieses Ziel notwendig sind - nicht mehr. D.h., jeder der neu verbauten L-Stücke muss mindestens ein Teilelement in der Grundschicht haben.

Mit deiner Formulierung würde man ausgehend von b (vier leere Felder) nur ein liegendes L-Stück betrachten - dieser eine Fall reicht aber nicht. unglücklich

Womöglich meinst du ja das richtige, aber du formulierst es falsch. Ist auch wirklich nicht einfach, wie du an meinen zahlreichen Editierungen merkst. Augenzwinkern

30.08.2021, 11:36

sonny1001

Auf diesen Beitrag antworten »

D.h.: ich nehme eine Vorbelegung (linke Seite der Gleichung) und dann

"Es sind ALLE Varianten zu betrachten, mit denen die 2x2-Grundschicht komplettiert werden kann oder aber eine andere Belegung der Grundschicht erreicht werden kann (das betrifft nur b und c). Dabei werden aber auch wirklich nur soviel L-Stücke verbaut, wie für dieses Ziel notwendig sind - nicht mehr. D.h., jeder der neu verbauten L-Stücke muss mindestens ein Teilelement in der Grundschicht haben."

Für die rechte Seite der Gleichung zähle ich dann welche Türme wie oft auf alle Varianten darauf passen.

30.08.2021, 11:49

HAL 9000

Auf diesen Beitrag antworten »

Ja, so kann man das sagen: Durch die eingebauten neuen L-Stücke ergibt sich ja eine neue Grundschicht (nur in Einzelfällen bei b und c) oder aber die Grundschicht ist komplettiert und es ergibt sich eine der 5 Varianten in der neuen Schicht, in Einzelfällen wird sogar auch schon diese Schicht komplettiert.

Man muss hier wirklich verdammt aufpassen, dass einem keine Variante entgeht UND aber auch keine mehrfach gezählt wird. Das ist die hohe Kunst bei einer derartigen Rekursionsaufstellung.

30.08.2021, 11:58

sonny1001

Auf diesen Beitrag antworten »

Danke, daß Du das so ausführlich mit mir diskutiert hast!

30.08.2021, 14:05

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht kann ja auch nochmal ein erfahrener Kombinatoriker (Huggy, Leopold, ...) einen Blick drauf werfen, womöglich habe ich doch irgendwo was vergessen oder zuviel gezählt: Da kann man manchmal zehnmal drauf schauen und trotzdem immer wieder den selben blinden Fleck haben.

---------------------------------------------------------------------------------------

Hab nochmal über die Systematik meiner Fallunterscheidungen der Rekursion nachgedacht, die kann man dann doch noch klarer gestalten mit einer einfacheren Grundregel:

Wir betrachten alle möglichen Ergänzungen mit L-Stücken, so dass die 2x2-Grundschicht komplett abgedeckt ist, und jedes dieser L-Stücke auch zu dieser Abdeckung beiträgt.

Die Rekursionsgleichungen ändern sich dadurch nur minimal, tatsächlich nur die erste:

$\begin{eqnarray*} b(n) = 12d(n-1)+4e(n-1) \end{eqnarray*}$ .
$\begin{eqnarray*} c(n) = b(n-1)+6f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} d(n) = 2c(n-1)+b(n-2) \end{eqnarray*}$
$\begin{eqnarray*} e(n) = 2b(n-2) \end{eqnarray*}$
$\begin{eqnarray*} f(n) = 2d(n-1) \end{eqnarray*}$

Start ist b(0)=c(1)=1 sowie b(1)=d(1)=e(1)=f(1)=0.

31.08.2021, 12:16

Huggy

Auf diesen Beitrag antworten »

Ja, das Zählen ist hier tückisch. Aber nach ein/zwei Stolperschritten bin ich auf dieselben Rekursionsgleichungen gekommen.

31.08.2021, 13:03

HAL 9000

Auf diesen Beitrag antworten »

Das ist dann einigermaßen beruhigend. Danke für's Nachprüfen! Freude

Neue Frage »

Antworten »

Rekurrenzgleichung für "L"-Turm

Verwandte Themen