Ułóż zależności rekurencyjne dla ciągów opisanych w następujący sposób:
a)\(a_{n}\) - liczba n-wyrazowych ciągów utworzonych z cyfr \({1,2,3,4,5}\), takich że bezpośrednio przed każdą z cyfr \(3,4,5\) stoi cyfra \(1\) ,
b) \(b_{n}\) - liczba sposobów, na które można zapełnić planszę o wymiarach \(3×n\) za pomocą klocków o wymiarach \(1×3\) i \( 2×3 \)(klocki można obracać).
Podaj uzasadnienie dla ułożonej rekurencji!
Nie mam pojęcia jak się za to zabrać , jak rozrysować
1.
Niech: \(p_n\) będzie liczbą n-elementowych ciągów kończących się cyfrą 1, oraz \(p_1=1\) \(q_n\) będzie liczbą n-elementowych ciągów kończących się cyfrą 2, oraz \(q_1=1\) \(r_n\) będzie liczbą n-elementowych ciągów kończących się cyframi 3,4 lub 5, oraz \(r_1=0\)
a wtedy: \(\begin{cases} p_n=p_{n-1}+q_{n-1}+r_{n-1} \\ q_n=p_{n-1}+q_{n-1}+r_{n-1} \\ r_n=3p_{n-1} \end{cases} \)
stąd \(p_n=2p_{n-1}+3p_{n-2}\) więc \(p_n=\frac{3^{n}-(-1)^{n}}{4}\) oraz \(a_n=p_n+q_n+r_n=2p_n+3p_{n-1}= \frac{3^{n+1}-(-1)^{n+1}}{4} \)
b.
Pole 3xN można pokryć jeśli:
1) do pokrytego pola 3x(N-1) dostawi się klocek 3x1
2) do pokrytego pola 3x(N-2) dostawi się klocek 3x2 (dostawienie dwóch klocków 3x1 było zliczane w pkt. 1) )
3) do pokrytego pola 3x(N-3) dostawi się leżące na sobie klocki 2x3 i 1x3 lub 1x3 i 2x3 lub trzy klocki 1x3(inne zestawy zakrywające pole 3x3 były zliczane w 1) i 2) )
stąd dla n>3 : \(b_n=b_{n-1}+b_{n-2}+3b_{n-3}\)
