arek1357 pisze: ↑25 mar 2009, o 20:33
dla n=3 podobnie 4*4*4- te w których A występuje obok siebie czyli jest ich 8 sztuk
nie będzie 8 sztuk tylko 7 (AAC, AAT, AAG, CAA,TAA,GAA,AAA), bo AAA w takim systemie zostało zliczone dwukrotnie (wbrew regule włączania - wyłączania).
Podobnie błędny jest wzór jawny
arek1357 pisze: ↑25 mar 2009, o 19:43\(\displaystyle{ a_{n}=4^{n}-(n-1)4^{n-2}}\)
bo nie uwzględnia reguły włączania-wyłączania
Pozdrawiam serdecznie
Tak, wiem, to bardzo stary temat. I chyba z genetyki.
Harry Xin pisze: ↑22 mar 2009, o 17:35
Ile jest ciągów długości n o wyrazach A, C, G, T takich, że A nie sąsiaduje z A? Zapisz zależność rekurencyjną.
Szukany ciąg n-wyrazowy dostanę przez dodanie do ciągów (n-1)-wyrazowych litery innej niż A, lub przez dodanie do ciągów (n-2)-wyrazowych jednego z trzech układów: CA. GA, TA. Stąd: \(\displaystyle{ S_n=3S_{n-1}+3S_{n-2}}\)
inaczej:
a_k - ilość ciągów zakończonych literą a
i_k - ilość ciągów niezakończonych literą a
Z układu : \(\displaystyle{ \begin{cases} a_n=i_{n-1} \\ i_n=3(a_{n-1}+i_{n-1}) \end{cases} }\)
mam: \(\displaystyle{ S_n=a_n+i_n=i_{n-1}+3(a_{n-1}+i_{n-1})=3(a_{n-2}+i_{n-2})+3S_{n-1}=3S_{n-2}+3S_{n-1}}\)
Podane w zadaniu rozwiązanie także jest poprawne gdyż: \(\displaystyle{ S_n=3S_{n-1}+3S_{n-2}=4S_{n-1} -S_{n-1}+3S_{n-2}=4S_{n-1} -(3S_{n-2}+3S_{n-3})+3S_{n-2}=4S_{n-1}-3S_{n-3}}\)
awd19 pisze: ↑13 mar 2012, o 18:04
Czy moglby ktos powiedziec, ile bedzie takich ciagow , w ktorych A wystepuje parzysta ilosc razy?
Ta ilość to: \(\displaystyle{ \sum_{i=1}^{\left[ \frac{n+1}{4} \right] }3^{n-2i} {n-2i+1 \choose 2i} }\)
Jeśli ktoś upiera się przy ciągach w których A występuje(?) zero razy, to niech zmieni sobie indeks dolny sigmy.