Kombinatorik?

Neue Frage »

eltzbett Auf diesen Beitrag antworten »
Kombinatorik?
Also ich habe eine Aufgabe bekommen, die, glaube ich, etwas mit Kombinatorik zu tun hat.

Aufgabe: "Aus Steinen der Länge 2 und Breite 1 wird ein zwei Einheiten breiter Weg der Länge 5, 6, 7, ..., n gepflastert. Wie viele verschiedene Pflasterungen gibt es?"

Dazu soll ich eine Struktur rausfinden. Ich habe mich erstmal mit Probieren an die Sache rangemacht (herauskam: N(2)=2; N(3)= 3; N(4)= 5; N(6)= 13; N(7)= 21...) und habe folgende Formel dabei erstellt:

N(n) = N(n-1) + N(n-2)
(N ist die Anzahl der Möglichkeiten, die Pflastersteine anzuordnen)

Das funktioniert aber nur, wenn n > 2 ist, und ich kann es auch nicht erklären, da ich es durch stures Zeichnen möglichen Kombinationen der Pflastersteine herausgefunden habe.
Kann mir hier jemand sagen, warum das so ist, ob das überhaupt richtig ist.
Ich frage mich auch, was ist, wenn n=100 ist, denn dann müsste man ja jedes N für 99,98,... berechnen.

Ich hoffe, das hört sich nicht allzu kompliziert an... und jemand kann mir helfen
AD Auf diesen Beitrag antworten »

Die Rekursionsformel ist richtig - und die kann man auch leicht begründen, wenn man sich überlegt, dass der letzte Stein nur quer oder längs liegen kann...

Was die Folge betrifft, das ist die bekannte Fibonacci-Folge. Musst du mal googeln, wikipedieren oder hier im Board suchen (müsste zig Treffer ergeben).
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »