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:

Für n = 1 => 2x1: 1 Möglichkeit

Für n = 2 => 2x2: 2 Möglichkeiten

Für n = 3 => 2x3: 3 Möglichkeiten

Für n = 4 => 2x4: 5 Möglichkeiten

an = an-1 + an-2

Ist das so richtig?

Oder ist die rekursive angabe für an+1, also an+1 = an + an-1?

Comments

Oder ist die rekursive angabe ....

Das ist egal, weil ja n eine "Laufvariable" ist.

Gruß Mathhilf

Answer 1

Zunächst mal besteht eine rekursive Darstellung auch immer aus den ersten Werten. Hier sollte es also lauten:

a1 = 1
a2 = 2

Meist möchte man ja ein a(n) wissen. Daher stellt man dieses meist in Form vorheriger Werte dar.

a(n) = a(n-1) + a(n-2) für n ∈ N, n > 2

Aber es wäre auch deine zweite Formulierung möglich oder gar

a(n+2) = a(n+1) + a(n) für n ∈ N, n > 0