Turm aus Dominosteinen (für mich als Abschluss)

31.08.2021, 13:53

sonny1001

Turm aus Dominosteinen (für mich als Abschluss)

Wie viele Möglichkeiten gibt es, einen Turm der Höhe n und Breite 3 aus Dominosteinen (1x2) zu bauen?

Lsg:
Belegung der untersten Schicht (o= nicht belegt, x=belegt):

b-Turm: ooo; c-Turm: xoo; d-Turm: xxo

Rekurrenzgleichungen:
b(n)=b(n-2)+2c(n-1)
c(n)=b(n-1)+d(n-1)
d(n)=b(n-2)+c(n-1)

Das führt zu:
b(n)=4b(n-2)+b(n-4), n>3; mit b(0)=1; b(1)=0; b(2)=3; b(3)=0

Die Anfangsbedingungen habe ich überprüft.

Daraus errechnet sich b(4)=13, was ich auch überprüft habe.

Zumindest ist bis hierhin alles stimmig.
Die explizite Bestimmung von b(n) ist mir zu aufwendig, da auch komplexe Zahlen vorkommen werden.
Vielleicht kann mir jemand die Rechnungen bestätigen?

31.08.2021, 15:33

HAL 9000

Auf diesen Beitrag antworten »

Mit den Rekurrenzgleichungen für $\begin{eqnarray*} b \end{eqnarray*}$ und $\begin{eqnarray*} c \end{eqnarray*}$ bin ich einverstanden, mit der für $\begin{eqnarray*} d \end{eqnarray*}$ nicht: Da sehe ich schlicht nur

$\begin{eqnarray*} d(n) = c(n-1) \end{eqnarray*}$

wenn nämlich ein Dominostein vertikal das eine noch leere Feld gesteckt wird, Punkt. Dein zusätzliches $\begin{eqnarray*} b(n-2) \end{eqnarray*}$ sieht mir verdächtig nach einer Mehrfachzählung aus. verwirrt

Zitat:

Original von sonny1001
Daraus errechnet sich b(4)=13, was ich auch überprüft habe.

Da bin ich gespannt: $\begin{eqnarray*} 3\cdot 3=9 \end{eqnarray*}$ Türme ergeben sich schnell, wenn man einfach zwei b(2)-Türme aufeinandersetzt.

Alle weiteren Türme besitzen "Verzahnungen" zwischen Schicht 2 und 3. Ich finde da nur zwei solche Türme:

665 566
345 543
342 243
112 211

Du anscheinend aber vier: Kannst du mir die zwei weiteren nennen?

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

Jedenfalls ergibt sich damit $\begin{eqnarray*} b(n) = 4b(n-2)-b(n-4) \end{eqnarray*}$ mit den Startwerten $\begin{eqnarray*} b(0)=1,b(2)=3 \end{eqnarray*}$ , und über die zugehörige charakteristische Gleichung $\begin{eqnarray*} \lambda^2-4\lambda+1=0 \end{eqnarray*}$ dann auch die explizite Darstellung

$\begin{eqnarray*} b(2k) = \frac{\left(3+\sqrt{3}\right)\cdot \left(2+\sqrt{3}\right)^k + \left(3-\sqrt{3}\right)\cdot \left(2-\sqrt{3}\right)^k}{6} = \left\lfloor \frac{3+\sqrt{3}}{6}\cdot \left(2+\sqrt{3}\right)^k + \frac{1}{2}\right\rfloor \end{eqnarray*}$ ;

für ungerade Indizes haben wir ja eh $\begin{eqnarray*} b(2k-1)=0 \end{eqnarray*}$ . Als kleines Formelmonster nenne ich mal noch eine geschlossene Anzahlformel, die für alle Turmhöhen gilt:

$\begin{eqnarray*} b(n) = \frac{1+(-1)^n}{12}\cdot \left[\left(3+\sqrt{3}\right)\cdot \left(\frac{\sqrt{6}+\sqrt{2}}{2}\right)^n + \left(3-\sqrt{3}\right)\cdot \left(\frac{\sqrt{6}-\sqrt{2}}{2}\right)^n\right] \end{eqnarray*}$

31.08.2021, 19:41

sonny1001

Auf diesen Beitrag antworten »

Ich habe die 13 Möglichkeiten im Anhang gezeichnet.

31.08.2021, 19:57

sonny1001

Auf diesen Beitrag antworten »

Schande auf mein Haupt ! Sehe gerade, daß ich einiges doppelt gezählt habe.

31.08.2021, 21:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat: