Znalezienie wzoru jawnego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Veranim
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 16 cze 2020, o 12:01
Płeć: Mężczyzna
wiek: 24
Podziękował: 3 razy

Znalezienie wzoru jawnego

Post autor: Veranim »

Witam, czy mógłbym prosić o pomoc z poniższym zadaniem?

Znaleźć wzór jawny na liczbę ciągów znaków długości \(\displaystyle{ n,n=1,2,3,...,}\) składających się z liter \(\displaystyle{ a,b,c}\) w których nie występuje układ liter \(\displaystyle{ cb}\)
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Znalezienie wzoru jawnego

Post autor: kerajs »

\(\displaystyle{ c_n}\) ilość ciągów długości n zakończonych literą c.
\(\displaystyle{ d_n}\) ilość ciągów długości n zakończonych literą a lub b.
Z układu:
\(\displaystyle{ \begin{cases} c_{n+1}=c_n+d_n \\ d_{n+1}=c_n+2d_n \end{cases} }\)
wyliczam:
\(\displaystyle{ c_n=A( \frac{3- \sqrt{5} }{2} )^n+B(\frac{3+ \sqrt{5} }{2} )^n}\)
Skoro \(\displaystyle{ c_1=1 \wedge c_2=3}\) to:
\(\displaystyle{ c_n= \frac{- \sqrt{5} }{5} (\frac{3- \sqrt{5} }{2} )^n+\frac{ \sqrt{5} }{5}(\frac{3- \sqrt{5} }{2})^n}\)
oraz \(\displaystyle{ d_n=c_{n+1}-c_n}\)
Szukana ilość ciągów długości n to:
\(\displaystyle{ s_n=c_n+d_n=c_{n+1}= \frac{- \sqrt{5} }{5} (\frac{3- \sqrt{5} }{2} )^{n+1}+\frac{ \sqrt{5} }{5}(\frac{3- \sqrt{5} }{2})^{n+1}}\)

PS
Sugeruję sprawdzić poprawność obliczeń.
ODPOWIEDZ