Niech \(\displaystyle{ \sum = {abc}}\) i niech \(\displaystyle{ s_n}\) oznacza liczbe słów dlugości n, które nie mają kolejnych liter a.
a) oblicz \(\displaystyle{ s_0 \ s_1 \ s_2}\)
\(\displaystyle{ s_0 \ = \ 1 \ , \ s_0=\{ \lambda\}}\)
\(\displaystyle{ s_1 \ = \ 3 \ , \ s_1=\{ \{a\}\{b\}\{c\}\}}\)
\(\displaystyle{ s_2 \ = \ 8 \ , \ s_1=\{ \{bb\}\{cc\}
\{ab\}\{ba\}
\{ac\}\{ca\}
\{bc\}\{cb\}\}}\)
b) Znajdź wzór rekurencyjny na \(\displaystyle{ s_n}\)
Gdyby nie było tego założenia: "...które nie mają kolejnych liter a"
to może taki wzór byłby prawidłowy:
\(\displaystyle{ s_{n+1}=3 s_{n}} \ \}\)
Po raz pierwszy spotykam się z takimi zadaniami, czy te rozwiązania które napisałem powyżej pokrywają się chodź trochę z prawdą?
