Ilość ciągów - zależność rekurencyjna

Harry Xin · Post autor: **Harry Xin** » 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ą.

gmpkm · Post autor: **gmpkm** » 22 mar 2009, o 19:23

Podpowiedź: Weź ciągi n-1 elementowe i wyrzuć te, które nie spełniają treści zadania.

Harry Xin · Post autor: **Harry Xin** » 22 mar 2009, o 19:35

Skoro mam wtedy \(\displaystyle{ \left(n-1\right)!}\) wszystkich możliwości ułożenia to w skrajnym przypadku A będzie na pierwszej, trzeciej, piątej etc. pozycji... Ale muszę też uwzględnić bardziej realne ułożenia. Jak to odjąć?
Szczerze mówiąc to czy mam n czy n-1 możliwości to niestety nie widzę w danej chwili różnicy...

gmpkm · Post autor: **gmpkm** » 22 mar 2009, o 19:45

Nie, nie, trzeba podejść z innej strony
Masz znaleźć zależność rekurencyjną, czyli dla Ciebie n-1 wyrazowych ciągów jest po prostu \(\displaystyle{ a_{n-1}}\), i one spełniają to, że nigdzie nie występuje dwójka "AA".
Załóżmy, że masz już ciągi n-1 elementowe, spełniające treść. Ciągów n elementowych jest 4 razy więcej, bo ostatnia litera jest dowolna, ale tylko po części. Teraz musisz odjąć niektóre ciągi. Które? I ile?

Harry Xin · Post autor: **Harry Xin** » 22 mar 2009, o 20:00

Które odrzucić? Te dla których w stosunku do n-1, gdy ostatnią literą było A dopisalibyśmy znowu A.
A ile... Hmmm... Tu będą pewnie potrzebne jakieś założenia. Myślę że dla co czwartego ciągu trzeba będzie odrzucić co czwarty nowy wyraz. Jak to zapisać i uściślić to nie mam pojęcia.
Chociaż dobrze myślę?

gmpkm · Post autor: **gmpkm** » 22 mar 2009, o 21:42

Hmm...
Trzeba odrzucić te ciągi, które kończą się na "AA". Rozważmy 3 ostatnie wyrazy ciagu n-elementowego. Ta ostatnia trójka jest postaci XAA, gdzie X oznacza jedną z liter C,T,G. Nie może być to litera A, bo założyliśmy, że ciągi, które liczyliśmy wcześniej spełniają treść zadania. Należy więc odjąć te ciągi, które kończą się niechcianą trójką. Tych ciągów jest \(\displaystyle{ 3 \cdot a_{n-3}}\), bo w miejsce litery X można wstawić jedną z trzech, a "początków" tego ciągu jest tyle ile ciągów n-3 elementowych spełniających treść zadania, czyli po prostu \(\displaystyle{ a_{n-3}}\)
Czy jest to w miarę jasne?

abc666 · Post autor: **abc666** » 22 mar 2009, o 21:59

żadne A ma nie sąsiadować z A

gmpkm · Post autor: **gmpkm** » 22 mar 2009, o 22:01

Ostatecznie będzie to \(\displaystyle{ a_{n} \ = \ 4a_{n-1} - 3a_{n-3}}\)-- 22 mar 2009, o 22:02 --

abc666 pisze:żadne A ma nie sąsiadować z A

No zgadzam się, ale rekurencja zapewnia, że do tej pory "A" nie sąsiaduje z "A"

Harry Xin · Post autor: **Harry Xin** » 23 mar 2009, o 11:26

gmpkm pisze:Czy jest to w miarę jasne?

Teraz wszystko jasne. Już rozumiem po co był nam ciąg n-1 - elementowy.
Dzięki!

arek1357 · Post autor: **arek1357** » 25 mar 2009, o 19:43

coś mi się nie zgadza bo wyszło mi prawdzie wzór jawny że możliwości jest:

\(\displaystyle{ a_{n}=4^{n}-(n-1)4^{n-2}}\)

co raczej nie odpowiada temu wzorowi rekurencyjnemu

bo dla n=1 będzie 4 możliwości, dla n=2 15 możliwości , n=3 już 56 możliwości itd...

Harry Xin · Post autor: **Harry Xin** » 25 mar 2009, o 20:05

Na ćwiczeniach powyższy wzór się potwierdził.

arek1357 · Post autor: **arek1357** » 25 mar 2009, o 20:33

To chyba mówimy o czymś innym bo np dla n=1
jest: A,G,C,T

dla n=2:

AG,AC,AT,GA,CA,TA,GC,GT,CG,TG,CT,TC,GG,CC,TT co daje 15

dla n=3 podobnie 4*4*4- te w których A występuje obok siebie czyli jest ich 8 sztuk

Harry Xin · Post autor: **Harry Xin** » 25 mar 2009, o 23:42

No zgadza się. Więc w czym problem?
Jeżeli chcesz sprawdzić na n=1,2,3, to możesz mieć wątpliwości. Prowadzący ćwiczenia przedstawił sprawę w ten sposób, że wzór zachodzi dla \(\displaystyle{ n\ge4}\)
No i jakby nie patrzeć jest to całkiem logiczne.

gmpkm · Post autor: **gmpkm** » 26 mar 2009, o 00:02

No tak, bo wzór rekurencyjny też zachodzi dopiero od czwartego wyrazu

-- 26 mar 2009, o 00:03 --

Pierwsze 3 wyrazy to tzw. warunki początkowe

arek1357 · Post autor: **arek1357** » 26 mar 2009, o 10:53

AAA teraz kumam