Matematyka.pl

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ą.

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

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...

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?

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ę?

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?

żadne A ma nie sąsiadować z A

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"

gmpkm pisze:Czy jest to w miarę jasne?

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

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...

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

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

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.

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

AAA teraz kumam