Układanie rekurencji

[Iza8723]

Ułóż zależności rekurencyjne dla ciągów opisanych w następujący sposób:

a) \(\displaystyle{ a_{n}}\) - liczba n-wyrazowych ciągów utworzonych z cyfr \(\displaystyle{ {1,2,3,4,5}}\), takich że bezpośrednio przed każdą z cyfr \(\displaystyle{ 3,4,5}\) stoi cyfra \(\displaystyle{ 1}\),
b) \(\displaystyle{ b_{n}}\) - liczba sposobów, na które można zapełnić planszę o wymiarach \(\displaystyle{ 3×n}\) za pomocą klocków o wymiarach \(\displaystyle{ 1×3}\) i \(\displaystyle{ 2×3 }\) (klocki można obracać).

Podaj uzasadnienie dla ułożonej rekurencji!

[kerajs]

1.
Niech:
\(\displaystyle{ p_n}\) będzie liczbą ciągów kończących się cyfrą 1, oraz \(\displaystyle{ p_1=1
}\)
\(\displaystyle{ q_n}\) będzie liczbą ciągów kończących się cyfrą 2, oraz \(\displaystyle{ q_1=1
}\)
\(\displaystyle{ r_n}\) będzie liczbą ciągów kończących się cyframi 3,4 lub 5, oraz \(\displaystyle{ r_1=0
}\)

a wtedy:
\(\displaystyle{ \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 \(\displaystyle{ p_n=2p_{n-1}+3p_{n-2}}\) więc \(\displaystyle{ p_n=\frac{3^{n}-(-1)^{n}}{4}}\) oraz \(\displaystyle{ a_n=p_n+q_n+r_n=2p_n+3p_{n-1}= \frac{3^{n+1}-(-1)^{n+1}}{4} }\)

[Premislav]

Zrobię przykład a), bo nie wymaga on wyobraźni, której jestem pozbawiony.
Niech \(\displaystyle{ b_{n}}\) będzie liczbą ciągów spełniających warunki zadania i kończących się jedynką, zaś \(\displaystyle{ c_{n}}\) – liczbą ciągów spełniających warunki zadania, lecz niekończących się jedynką. Oczywiście mamy \(\displaystyle{ b_{n}+c_{n}=a_{n}}\), a ponadto
\(\displaystyle{ a_{n+1}=5b_{n}+2c_{n}}\)
Interpretacja tego jest prosta: jeśli ciąg długości \(\displaystyle{ n}\) spełniający warunki zadania kończył się jedynką, to możemy do niego dopisać na końcu jeszcze jeden wyraz z \(\displaystyle{ \left\{1,2,3,4,5\right\}}\) na pięć sposobów, otrzymując w ten sposób ciąg długości \(\displaystyle{ n+1}\) czyniący zadość warunkom zadania, a jeśli nie kończył się jedynką, to możemy dopisać tylko jedynkę albo dwójkę, czyli dwie możliwości.
Pozostaje zauważyć jeszcze jedną zależność, a mianowicie \(\displaystyle{ b_{n+1}=a_{n}}\). Istotnie, przez dopisanie jedynki na końcu ciągu długości \(\displaystyle{ n}\) spełniającego warunki zadania dostajemy ciąg spełniający warunki zadania i kończący się jedynką. Z drugiej strony jeśli mamy ciąg długości \(\displaystyle{ n+1}\) czyniący zadość warunkom zadania, to jego dowolny prefiks też spełnia warunki zadania, w szczególności prefiks do n-tego wyrazu włącznie.
Otrzymujemy zatem:
\(\displaystyle{ a_{n+1}=5b_{n}+2c_{n}=5b_{n}+2(a_{n}-b_{n})=2a_{n}+3b_{n}=2a_{n}+3a_{n-1}}\)

[Iza8723]

Super, dziękuję bardzo za wytłumaczenie.
A macie pomysł jak zacząć podpunkt b)?

[kerajs]

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 (inne zestawy zakrywające pole 3x3 były zliczane w 1) i 2) )
stąd dla \(\displaystyle{ n>3}\) :
\(\displaystyle{ b_n=b_{n-1}+b_{n-2}+2b_{n-3}}\)

Ponadto z rysunków mam:
\(\displaystyle{ b_1=1\\
b_2=2\\
b_3=6}\)
Wzór ogólny to: \(\displaystyle{ b_n=A2^n+B\sin (n \cdot \frac{2 \pi }{3}) +C \cos (n \cdot \frac{2 \pi }{3}) }\)
Pozostaje wyliczyć stałe A, B i C.

Dodano po 4 godzinach 46 minutach 53 sekundach:
Sorry, zgubiłem jedno ustawienie.
Powinno być:
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 \(\displaystyle{ n>3}\) :
\(\displaystyle{ b_n=b_{n-1}+b_{n-2}+\color{red}{3}\color{black}{b_{n-3}}}\)

Ponadto z rysunków mam:
\(\displaystyle{ b_1=1\\
b_2=2\\
b_3=6}\)
Ponieważ równanie \(\displaystyle{ r^3=r^2+r+3}\) nie ma sensownych pierwiastków, to odpuszczam szukanie wzoru jawnego (którego zresztą w zadaniu nie wymagają).
Sorki za wprowadzenie w błąd.