ułożyć wzór rekurencyjny
: 15 wrz 2009, o 15:07
Na ile sposobów można ułożyć chodnik długości n jednostek mając do dyspozycji niebieskie płytki długości jednej jednostki oraz zielone i czerwone płytki długości dwóch jednostek.
\(\displaystyle{ h_n}\) - liczba możliwych ułożeń chodnika o długości \(\displaystyle{ n}\)
\(\displaystyle{ h_n = h_{n-1} + 2h_{n-2}}\)
Do chodnika o długości \(\displaystyle{ n-1}\) możemy dołożyć tylko jedną płytkę o długości \(\displaystyle{ 1}\), a do chodnika o długości \(\displaystyle{ n-2}\) możemy dołożyć jedną z dwóch płytek o długości \(\displaystyle{ 2}\).
Nie rozpatrujemy przypadku dołożenia dwóch płytek o długości \(\displaystyle{ 1}\), ponieważ dokładając jedną taką płytkę otrzymujemy przypadek chodnika o długości \(\displaystyle{ n-1}\).