szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 lis 2017, o 22:05 
Użytkownik

Posty: 7
Lokalizacja: Polska
Znajdz równanie rekurencyjne dla liczby n-elementowych ciagów ternarnych, w których:
(a) liczba zer jest parzysta,
(b) liczba zer i liczba jedynek sa parzyste
dla liczb \{0,1,2\}

W przykładzie a wyszło mi
3^{n-1} + S_{n-1}

Ponieważ 0 v 1 v 2
dla 1 i 2 będzie S_{n-1} a dla 0
3^{n-1} + S_{n-1}
Gdy od wszystkich mozliwosci w danym n odejmiemy mozliwosci parzyste z 0 zostana same nie parzyste i gdy dodamy jedno 0 otrzymamy parzysta ilosc zer.
Czy dobrze rozumiem ?
Z góry dziękuje serdecznie za pomoc !
Góra
Mężczyzna Online
PostNapisane: 22 lis 2017, o 02:23 
Użytkownik

Posty: 12875
(a)
Oznaczmy przez S_n liczbę ciągów ternarnych o n wyrazach spełniających warunki, jak u Ciebie;
jeśli w ciągu ternarnym o n wyrazach jest parzyście wiele zer, to dopisując dowolną liczbę z \left\{ 0,1,2\right\} różną od zera (tj. jedynkę bądź dwójkę) dalej otrzymamy parzyście wiele zer. Natomiast jeśli w n-wyrazowym ciągu jest nieparzyście wiele zer, to dopisując na końcu zero, mamy ciąg n+1-wyrazowy o parzystej liczbie zer. Wszystkich n-wyrazowych ciągów ternarnych jest oczywiście 3^n. Zatem:
S_{n+1}=2\cdot S_n+1\cdot (3^n-S_n)=3^n+S_n, tj. S_n=3^{n-1}+S_{n-1}, zgadza się.

b)
To już trudniejsze. Jest 3^n ciągów ternarnych długości n, powiedzmy, że z tego mamy S_n ciągów, w których jest zarówno parzyście wiele zer, jak i parzyście wiele jedynek.
Zatem mamy 3^n-S_n ciągów ternarnych długości n, które nam nie pasują. Wszędzie dalej są ciągi ternarne długości n. Oznaczmy przez X_n liczbę tych ciągów, które mają parzyście wiele zer, ale nieparzyście wiele jedynek, przez Y_n liczbę ciągów o nieparzyście wielu zerach i parzyście wielu jedynkach oraz przez Z_n liczbę ciągów o nieparzyście wielu zerach i nieparzyście wielu jedynkach. Oczywiście jest
3^n-S_n=X_n+Y_n+Z_n
Ponadto mamy
(1) X_{n+1}=X_n+S_n+Z_n
Wyjaśnienie: patrzymy, w jaki sposób z ciągu długości n możemy zrobić ciąg długości n+1 mający parzyście wiele zer, lecz nieparzyście wiele jedynek. Do spełniającego ten warunek n-wyrazowego dopisujemy dwójkę, do mającego zarówno parzyście wiele zer, jak i parzyście wiele jedynek dopisujemy jedynkę, do mającego nieparzyście wiele zer i nieparzyście wiele jedynek dopisujemy zero.
Jest także
(2) Y_{n+1}=Y_n+S_n+Z_n - zupełnie analogicznie, jak z X_n, a ponadto
(3) Z_{n+1}=X_n+Y_n+Z_n
- do n-wyrazowego ciągu o parzyście wielu zerach i nieparzyście wielu jedynkach dopisujemy na końcu zero, do n-wyrazowego ciągu o nieparzyście wielu zerach i parzyście wielu jedynkach dopisujemy na końcu jedynkę, do n-wyrazowego ciągu o nieparzyście wielu zerach i nieparzyście wielu jedynkach dopisujemy na końcu dwójkę.
Po dodaniu stronami zależności rekurencyjnych (1), (2), (3) dostajemy
X_{n+1}+Y_{n+1}+Z_{n+1}=2S_n+2(X_n+Y_n+Z_n)+Z_n
i teraz korzystając dwukrotnie z: 3^n-S_n=X_n+Y_n+Z_n otrzymujemy
3^{n+1}-S_{n+1}=2S_n+2(3^n-S_n)+Z_n
czyli
S_{n+1}=3^n-Z_n
Z drugiej strony, wykorzystując powyższe zależności mamy
Z_{n+1}=X_n+Y_n+Z_n=3^n-S_n, czyli
Z_n=3^{n-1}-S_{n-1}
i ostatecznie
S_{n+1}=3^n-Z_n=3^n-3^{n-1}+S_{n-1}=2\cdot 3^{n-1}+S_{n-1}


Uff, trochę się napracowałem. Zapewne da się to ładniej zrobić, ale trzeba mieć mózg, ja niestety nie spełniam tego warunku.
Góra
Mężczyzna Offline
PostNapisane: 22 lis 2017, o 11:26 
Użytkownik
Avatar użytkownika

Posty: 3378
Lokalizacja: blisko
Tak na szybkiego a propo b) dołożę swoje trzy grosze ale na wzór jawny tzn. na funkcję charakterystyczną:

sugestia, że ilość możliwości powinno być:

a_{n}= \sum_{2x+2y+z=n}^{}  \frac{n!}{(2x)!(2y)!z!}

lub:

n! \sum_{}^{}  \frac{1}{(2i)!(2j)!(n-2i-2j)!}

co sugeruje nam takową funkcję:

(1+ \frac{1}{2!}x^2+ \frac{1}{4!}x^4+ \frac{1}{6!}x^6+.....)^2(1+x+ \frac{1}{2!}x^2+ \frac{1}{3!}x^3+...)


co daje nam funkcję charakterystyczną:

f(x)=e^x \left( \sum_{n=0}^{ \infty } \frac{1}{(2n)!}x^{2n}\right)^2 = e^x \frac{\left( e^{-x}+e^x\right)^2 }{4}

zwinąć rozłożyć a wynik pomnożyć przez: n!

jak rozłożymy tę funkcję w szereg otrzymamy:

f(x)= \frac{e^{-x}+2e^x+e^{3x}}{4}= \frac{1}{4} \sum_{n=0}^{ \infty } \frac{3^n+(-1)^n+2}{n!}x^n

więc nasz ciąg powinien wyglądać następująco:


a_{n}= \frac{3^n+(-1)^n+2}{4}

Ja może przeproszę bo się tu dowaliłem niechcący i nie zrobiłem tak jak trzeba bo trzeba było znaleźć wzór
rekurencyjny a nie jawny, ale można z jawnego w końcu przejść do rekurencji którą tak pięknie zrobił Premislaw. (Po co mam powielać Premislawa jest niepowtarzalny). Szkoda że nie napisałeś w swoim wzorze wartości początkowe tznS_{0}, S_{1}.

Wtedy indukcyjnie można udowodnić równoważność tych wzorów.

Tylko ja użyłem zmiennej a_{n}.

Ale się poprawię i napiszę:

mój:

S_{n}= \frac{3^n+(-1)^n+2}{4}

Premislawa:

S_{n+1}=S_{n-1}+2 \cdot 3^{n-1}



Spróbujmy udowodnić równoważność tych wzorów, przepiszę wzór Premislawa:

S_{n+1}-S_{n-1}=2 \cdot 3^{n-1}

a teraz moje:

S_{n+1}-S_{n-1}= \frac{3^{n+1}+(-1)^{n+1}+2-3^{n-1}-(-1)^{n-1}-2}{4}= \frac{ \frac{8}{3} \cdot 3^n-(-1)^n+(-1)^n }{4}=2 \cdot 3^{n-1}

Więc się zgadza wzory są równoważne brawa dla Premislawa...

Niech tylko dopisze warunki początkowe(Bo chyba S_{0} nie ma sensu) a dostanie owacje na stojąco...


poprawiłem...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ustawianie osob w rzedzie, liczby n-cyfrowe itp  Anonymous  16
 Znajdź a_n wyraz rozwinięcia dwumianu  Anonymous  1
 równanie z symbolem newtona.  apacz  5
 [zadanie] Rozwiąż równanie  My4tic  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl