Niech \(\displaystyle{ \Sigma=\{a , b, c\}}\) i niech \(\displaystyle{ s_{n}}\) oznacza liczbę słów długości n w alfabecie S , w których nie występuje ciąg aa. Znaleźć dla niego wzór rekurencyjny.
wiem ze \(\displaystyle{ f(n)=2f(n-1) + ...}\) bo do każdego słowa utworzonego poprzednio można dodać zarówno b jak i c i warunki będą spełnione. Ile jest słow które mają a na końcu?
rekurencja
-
max
- Użytkownik
- Posty: 3242
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
rekurencja
Zauważ, że słowa, które kończą się \(\displaystyle{ a}\), to słowa, które na przedostatniej pozycji mają \(\displaystyle{ b}\) lub \(\displaystyle{ c}\), czyli słowa, do których 'krok wcześniej' dopisaliśmy \(\displaystyle{ b}\) lub \(\displaystyle{ c}\), a liczba takich słów wynosi:
\(\displaystyle{ 2s_{n - 2}}\)
Zakładając, że istnieje słowo zerowej długości otrzymujemy rekurencję:
\(\displaystyle{ \left\{\begin{array}{l} s_0 = 1 \\ s_1 = 3 \\ s_{n} = 2\big(s_{n - 1} + s_{n - 2}\big) , \ n \geqslant 2 \end{array}\right.}\)
\(\displaystyle{ 2s_{n - 2}}\)
Zakładając, że istnieje słowo zerowej długości otrzymujemy rekurencję:
\(\displaystyle{ \left\{\begin{array}{l} s_0 = 1 \\ s_1 = 3 \\ s_{n} = 2\big(s_{n - 1} + s_{n - 2}\big) , \ n \geqslant 2 \end{array}\right.}\)