znaleźć jawny wzór
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
znaleźć jawny wzór
znaleźć jawny wzór na liczbę ciągów znaków długości n, n=1,2,3,..., składających się z liter a,b,c w których nie występuje układ liter ac.
-
kerajs
- Fachowiec
- Posty: 2963
- Rejestracja: 14 lis 2016, 14:38
- Podziękowania: 33 razy
- Otrzymane podziękowania: 1303 razy
- Płeć:
Re: znaleźć jawny wzór
\(a_n\) ilość ciągów długości n zakończonych literą a.
\(d_n\) ilość ciągów długości n zakończonych literą b lub c.
Z układu:
\( \begin{cases} a_{n+1}=a_n+d_n \\ d_{n+1}=a_n+2d_n \end{cases} \)
wyliczam:
\(a_n=A( \frac{3- \sqrt{5} }{2} )^n+B(\frac{3+ \sqrt{5} }{2} )^n\)
Skoro \(a_1=1 \wedge a_2=3\) to:
\(a_n= \frac{- \sqrt{5} }{5} (\frac{3- \sqrt{5} }{2} )^n+\frac{ \sqrt{5} }{5}(\frac{3- \sqrt{5} }{2})^n\)
oraz \(d_n=a_{n+1}-a_n=\)
Szukana ilość ciągów długości n to:
\(s_n=a_n+d_n=a_{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ń.
\(d_n\) ilość ciągów długości n zakończonych literą b lub c.
Z układu:
\( \begin{cases} a_{n+1}=a_n+d_n \\ d_{n+1}=a_n+2d_n \end{cases} \)
wyliczam:
\(a_n=A( \frac{3- \sqrt{5} }{2} )^n+B(\frac{3+ \sqrt{5} }{2} )^n\)
Skoro \(a_1=1 \wedge a_2=3\) to:
\(a_n= \frac{- \sqrt{5} }{5} (\frac{3- \sqrt{5} }{2} )^n+\frac{ \sqrt{5} }{5}(\frac{3- \sqrt{5} }{2})^n\)
oraz \(d_n=a_{n+1}-a_n=\)
Szukana ilość ciągów długości n to:
\(s_n=a_n+d_n=a_{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ń.