Wiskundeforum

Hi,

Ik zit met een klein probleempje... Ik probeer een "spelbord" van 2xn vakjes op te vullen met blokjes van het formaat 2x1 en 2x2. (draaien van de blokjes is toegelaten). Nu is de vraag: op hoeveel verschillende manieren kan je dit doen?
Als je enkel 2x1 blokjes hebt, is dit probleem niet moeilijk op te lossen: het aantal mogelijkheden volgt de rij van Fibonacci. Als je echter ook 2x2 blokjes krijgt, is het systeem precies een beetje zoek.

Weet er iemand hier welk algoritme erachter zit? Of kan iemand mij een idee geven van hoe ik zoiets kan/zou moeten vinden? Ik heb al geprobeerd het te tekenen en de mogelijkheden te tellen, maar het worden er al vrij snel vrij veel, en dat werkte dus niet.

Mijn Getallen Tot Nu Toe:
bordformaat =
2x1 => 1 mogelijkheid
2x2 => 3 mogelijkheden
2x3 => 5 mogelijkheden
2x4 => 11 mogelijkheden
En verder ben ik al niet meer zeker of ze nog wel kloppen...
(wat betreft het algoritme: afwisselen van "*2,+1" en "*2,-1" werkte niet)

Ik zit echt helemaal vast en ik heb dit nodig voor een programma dat ik aan het schrijven ben... Help?

Je kan simpel beginnen:

Stel je hebt een gebied van . Je kan dan op 3 manieren beginnen:
- een blokje.
- twee blokjes boven elkaar.
- een blokje.

In elk van de gevallen moet je je afvragen: hoeveel blijft er over? De formules worden ietwat ingewikkelder dan bij alleen de blokjes, maar het is even goed op te lossen.