Witam wszystkich, jestem trochę w plecy z matematyką dyskretną u mnie na uczelni i byłbym wdzięczny jak by ktoś naświetlił na przykładzie poniższych zadań jak je rozwiązywać.
Pozdrawiam i z góry dziękuję.
1. \(\displaystyle{ \Sigma =\{a,b\}}\), \(\displaystyle{ s_{n}=}\) liczba słów nie zawierająca liter ab
a) Obliczyć \(\displaystyle{ s_{0} ,\ s_{1} ,\ s_{2} ,\ s_{3}.}\)
b) wyznaczyć wzór jawny na \(\displaystyle{ s_{n}}\)
2. Niech \(\displaystyle{ s_{n}=s_{n-1}+2s_{n-2} \ ; \ n \ge 2}\) \(\displaystyle{ s_{0}=1 \ s_{1}=1}\)
a) obliczyć rekurencyjnie\(\displaystyle{ s_{6}}\)
b) wyznaczyć wzór jawny na \(\displaystyle{ s_{n}}\)
c) wykazać że wszystkie wyrazy ciągu \(\displaystyle{ s_{n}}\) są nieparzyste
3. \(\displaystyle{ \Sigma =\{a,b\}}\)
\(\displaystyle{ \Sigma^{*}}\) zbiór wszystkich słów zbudowanych z alfabetu \(\displaystyle{ \Sigma}\)
\(\displaystyle{ \Sigma^{k}=\{w\in \Sigma^{*}:dlugosc(w)=k\}}\)
Niech \(\displaystyle{ A_{n}}\) oznacza zbiór słów długości n, w których nie występują kolejno litery aa, a więc: \(\displaystyle{ A_{0} =\{\lambda\}, \ A_{1} =\{a,b\}, \ A_{2} =\{ab,ba,bb \}}\)
niech \(\displaystyle{ s_{n}}\) oznacza liczbę słów z zbioru \(\displaystyle{ A_{n}, \ s_{0}=1, \ s_{1}=2, \ s_{2}=3}\)
a)wyznaczyć wzór rekurencyjny na \(\displaystyle{ s_{n}}\).
b)Niech \(\displaystyle{ t_{n}}\) oznacza liczbę słów długości n w których jest parzysta liczba litery a.
\(\displaystyle{ t_{n}=}\) liczba elementów zbioru \(\displaystyle{ B_{n}= \{w\in \Sigma^{n}: \ w \ ma \ parzysta \ liczbe \ liter \ a\}}\)
\(\displaystyle{ B_{0} =\{\lambda\}}\)
\(\displaystyle{ B_{1} =\{b\}}\)
\(\displaystyle{ B_{2} =\{aa,bb\}}\)
\(\displaystyle{ B_{3} =\{aab,baa,aba,bbb\}}\)
\(\displaystyle{ t_{0} =\{1\}}\)
\(\displaystyle{ t_{1} =\{1\}}\)
\(\displaystyle{ t_{2} =\{2\}}\)
\(\displaystyle{ t_{3} =\{4\}}\)
Wyznacz wzór rekurencyjny na \(\displaystyle{ t_{n}}\)