Znajdz równanie rekurencyjne dla liczby \(\displaystyle{ n}\)-elementowych ciagów ternarnych, w których:
(a) liczba zer jest parzysta,
(b) liczba zer i liczba jedynek sa parzyste
dla liczb \(\displaystyle{ \{0,1,2\}}\)
W przykładzie a wyszło mi
\(\displaystyle{ 3^{n-1} + S_{n-1}}\)
Ponieważ 0 v 1 v 2
dla 1 i 2 będzie \(\displaystyle{ S_{n-1}}\) a dla 0
\(\displaystyle{ 3^{n-1} + S_{n-1}}\)
Gdy od wszystkich mozliwosci w danym n odejmiemy mozliwosci parzyste z \(\displaystyle{ 0}\) zostana same nie parzyste i gdy dodamy jedno \(\displaystyle{ 0}\) otrzymamy parzysta ilosc zer.
Czy dobrze rozumiem ?
Z góry dziękuje serdecznie za pomoc !
Znajdz równanie rekurencyjne dla liczby n-elementowych ciagó
-
- Użytkownik
- Posty: 7
- Rejestracja: 21 lis 2017, o 22:01
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
Znajdz równanie rekurencyjne dla liczby n-elementowych ciagó
Ostatnio zmieniony 21 lis 2017, o 22:44 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Znajdz równanie rekurencyjne dla liczby n-elementowych c
(a)
Oznaczmy przez \(\displaystyle{ S_n}\) liczbę ciągów ternarnych o \(\displaystyle{ n}\) wyrazach spełniających warunki, jak u Ciebie;
jeśli w ciągu ternarnym o \(\displaystyle{ n}\) wyrazach jest parzyście wiele zer, to dopisując dowolną liczbę z \(\displaystyle{ \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 \(\displaystyle{ n+1}\)-wyrazowy o parzystej liczbie zer. Wszystkich n-wyrazowych ciągów ternarnych jest oczywiście \(\displaystyle{ 3^n}\). Zatem:
\(\displaystyle{ 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 \(\displaystyle{ 3^n}\) ciągów ternarnych długości \(\displaystyle{ n}\), powiedzmy, że z tego mamy \(\displaystyle{ S_n}\) ciągów, w których jest zarówno parzyście wiele zer, jak i parzyście wiele jedynek.
Zatem mamy \(\displaystyle{ 3^n-S_n}\) ciągów ternarnych długości \(\displaystyle{ n}\), które nam nie pasują. Wszędzie dalej są ciągi ternarne długości \(\displaystyle{ n}\). Oznaczmy przez \(\displaystyle{ X_n}\) liczbę tych ciągów, które mają parzyście wiele zer, ale nieparzyście wiele jedynek, przez \(\displaystyle{ Y_n}\) liczbę ciągów o nieparzyście wielu zerach i parzyście wielu jedynkach oraz przez \(\displaystyle{ Z_n}\) liczbę ciągów o nieparzyście wielu zerach i nieparzyście wielu jedynkach. Oczywiście jest
\(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\)
Ponadto mamy
(1) \(\displaystyle{ X_{n+1}=X_n+S_n+Z_n}\)
Wyjaśnienie: patrzymy, w jaki sposób z ciągu długości \(\displaystyle{ n}\) możemy zrobić ciąg długości \(\displaystyle{ 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) \(\displaystyle{ Y_{n+1}=Y_n+S_n+Z_n}\) - zupełnie analogicznie, jak z \(\displaystyle{ X_n}\), a ponadto
(3) \(\displaystyle{ 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
\(\displaystyle{ 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: \(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\) otrzymujemy
\(\displaystyle{ 3^{n+1}-S_{n+1}=2S_n+2(3^n-S_n)+Z_n}\)
czyli
\(\displaystyle{ S_{n+1}=3^n-Z_n}\)
Z drugiej strony, wykorzystując powyższe zależności mamy
\(\displaystyle{ Z_{n+1}=X_n+Y_n+Z_n=3^n-S_n}\), czyli
\(\displaystyle{ Z_n=3^{n-1}-S_{n-1}}\)
i ostatecznie
\(\displaystyle{ 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.
Oznaczmy przez \(\displaystyle{ S_n}\) liczbę ciągów ternarnych o \(\displaystyle{ n}\) wyrazach spełniających warunki, jak u Ciebie;
jeśli w ciągu ternarnym o \(\displaystyle{ n}\) wyrazach jest parzyście wiele zer, to dopisując dowolną liczbę z \(\displaystyle{ \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 \(\displaystyle{ n+1}\)-wyrazowy o parzystej liczbie zer. Wszystkich n-wyrazowych ciągów ternarnych jest oczywiście \(\displaystyle{ 3^n}\). Zatem:
\(\displaystyle{ 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 \(\displaystyle{ 3^n}\) ciągów ternarnych długości \(\displaystyle{ n}\), powiedzmy, że z tego mamy \(\displaystyle{ S_n}\) ciągów, w których jest zarówno parzyście wiele zer, jak i parzyście wiele jedynek.
Zatem mamy \(\displaystyle{ 3^n-S_n}\) ciągów ternarnych długości \(\displaystyle{ n}\), które nam nie pasują. Wszędzie dalej są ciągi ternarne długości \(\displaystyle{ n}\). Oznaczmy przez \(\displaystyle{ X_n}\) liczbę tych ciągów, które mają parzyście wiele zer, ale nieparzyście wiele jedynek, przez \(\displaystyle{ Y_n}\) liczbę ciągów o nieparzyście wielu zerach i parzyście wielu jedynkach oraz przez \(\displaystyle{ Z_n}\) liczbę ciągów o nieparzyście wielu zerach i nieparzyście wielu jedynkach. Oczywiście jest
\(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\)
Ponadto mamy
(1) \(\displaystyle{ X_{n+1}=X_n+S_n+Z_n}\)
Wyjaśnienie: patrzymy, w jaki sposób z ciągu długości \(\displaystyle{ n}\) możemy zrobić ciąg długości \(\displaystyle{ 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) \(\displaystyle{ Y_{n+1}=Y_n+S_n+Z_n}\) - zupełnie analogicznie, jak z \(\displaystyle{ X_n}\), a ponadto
(3) \(\displaystyle{ 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
\(\displaystyle{ 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: \(\displaystyle{ 3^n-S_n=X_n+Y_n+Z_n}\) otrzymujemy
\(\displaystyle{ 3^{n+1}-S_{n+1}=2S_n+2(3^n-S_n)+Z_n}\)
czyli
\(\displaystyle{ S_{n+1}=3^n-Z_n}\)
Z drugiej strony, wykorzystując powyższe zależności mamy
\(\displaystyle{ Z_{n+1}=X_n+Y_n+Z_n=3^n-S_n}\), czyli
\(\displaystyle{ Z_n=3^{n-1}-S_{n-1}}\)
i ostatecznie
\(\displaystyle{ 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.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Znajdz równanie rekurencyjne dla liczby n-elementowych c
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ć:
\(\displaystyle{ a_{n}= \sum_{2x+2y+z=n}^{} \frac{n!}{(2x)!(2y)!z!}}\)
lub:
\(\displaystyle{ n! \sum_{}^{} \frac{1}{(2i)!(2j)!(n-2i-2j)!}}\)
co sugeruje nam takową funkcję:
\(\displaystyle{ (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ą:
\(\displaystyle{ 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: \(\displaystyle{ n!}\)
jak rozłożymy tę funkcję w szereg otrzymamy:
\(\displaystyle{ 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:
\(\displaystyle{ 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 tzn\(\displaystyle{ S_{0}, S_{1}}\).
Wtedy indukcyjnie można udowodnić równoważność tych wzorów.
Tylko ja użyłem zmiennej \(\displaystyle{ a_{n}}\).
Ale się poprawię i napiszę:
mój:
\(\displaystyle{ S_{n}= \frac{3^n+(-1)^n+2}{4}}\)
Premislawa:
\(\displaystyle{ S_{n+1}=S_{n-1}+2 \cdot 3^{n-1}}\)
Spróbujmy udowodnić równoważność tych wzorów, przepiszę wzór Premislawa:
\(\displaystyle{ S_{n+1}-S_{n-1}=2 \cdot 3^{n-1}}\)
a teraz moje:
\(\displaystyle{ 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 \(\displaystyle{ S_{0}}\) nie ma sensu) a dostanie owacje na stojąco...
poprawiłem...
sugestia, że ilość możliwości powinno być:
\(\displaystyle{ a_{n}= \sum_{2x+2y+z=n}^{} \frac{n!}{(2x)!(2y)!z!}}\)
lub:
\(\displaystyle{ n! \sum_{}^{} \frac{1}{(2i)!(2j)!(n-2i-2j)!}}\)
co sugeruje nam takową funkcję:
\(\displaystyle{ (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ą:
\(\displaystyle{ 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: \(\displaystyle{ n!}\)
jak rozłożymy tę funkcję w szereg otrzymamy:
\(\displaystyle{ 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:
\(\displaystyle{ 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 tzn\(\displaystyle{ S_{0}, S_{1}}\).
Wtedy indukcyjnie można udowodnić równoważność tych wzorów.
Tylko ja użyłem zmiennej \(\displaystyle{ a_{n}}\).
Ale się poprawię i napiszę:
mój:
\(\displaystyle{ S_{n}= \frac{3^n+(-1)^n+2}{4}}\)
Premislawa:
\(\displaystyle{ S_{n+1}=S_{n-1}+2 \cdot 3^{n-1}}\)
Spróbujmy udowodnić równoważność tych wzorów, przepiszę wzór Premislawa:
\(\displaystyle{ S_{n+1}-S_{n-1}=2 \cdot 3^{n-1}}\)
a teraz moje:
\(\displaystyle{ 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 \(\displaystyle{ S_{0}}\) nie ma sensu) a dostanie owacje na stojąco...
poprawiłem...