rekursiv: Auf wie viele Arten kann man ein Rechteck der Größe 2 x n mit Dominosteinen der Größe 1 x 2 pflastern?

Question

Aufgabe:

Lösen Sie folgendes Problem rekursiv: Auf wie viele Arten
kann man ein Rechteck der Größe 2 x n mit Dominosteinen der Größe 1 x 2
pflastern? Unter „pflastern“ ist dabei Folgendes zu verstehen: Das Rechteck soll so
bedeckt werden, dass sich keine zwei Dominosteine überlappen und sie nicht über
den Rand hinausragen.

Problem/Ansatz:

Hallo,

ist meine Lösung im Anhang so richtig?

Liebe Grüße

Comments

Werden zwei Pflasterungen unterschieden, wenn sich die Lage der Dominosteine ändert:

Sind alle Dominosteine verschieden?

---

Wie meinst du das? Ich glaube, es geht nur darum, Rechteck 2 x n auszufüllen mit den Steinen, oder? Also wenn ich z.B. bei n = 3 die erste Möglichkeit betrachte, ist es egal, ob sie auf dem Kopf stehen oder gerade, es ist trotztdem nur "eine" Möglichkeit. So verstand ich es zumindest.

Answer 1

Für n=4 gibt es 5 Möglichkeiten!

Du kannst entweder

an die Möglichkeiten für n=3 waagerecht anlegen

oder

an die Möglichkeiten für n=3 einen Stein hochkant anlegen.

Comments

Wie meinst du das? Wie sieht die 5. Möglichkeit denn aus? Durch anlegen auf n=3 würden doch keine Rechtecke rauskommen, außer wenn ich vertikal anlege. Ich glaube du meinst an die zweite Möglichkeit für n = 3 kann ich von links vertikal anlegen.

Und dann wäre es die fibonacci folge.

Answer 2

für n=4 gibt es diese Möglichkeiten:

Answer 3

Du sollst das Ganze rekursiv lösen und nicht irgendwelchen kombinatorischen Schwachsinn machen.

Um ein 7x2 zu bekommen, kannst Du entweder einen senkrecht an ein 6x2 anlegen, oder zwei waagrecht an ein 5x2 anlegen.

Nenne ein $n \times 2$-Rechteck $a_n$. Dann gilt hier $a_7 = a_6+a_5$ und allgemein $a_n = a_{n-1}+a_{n-2}$.

Und wie Du schon erkannt hast, ist das die Fibonacci-Folge.