Witam,
próbuję rozwiązać zadanie dla sekwencji zero-jedynkowej o dowolnej długości \(\displaystyle{ n}\),
gdzie \(\displaystyle{ P( x_{i} =1) = \frac12}\). Muszę obliczyć prawdopodobieństwo, że sekwencja zawiera tylko jedną parę
\(\displaystyle{ x_{i} i x_{i+1}}\) taką, że \(\displaystyle{ x_{i} =1}\) i \(\displaystyle{ x_{i+1} =1}\).
Mogę Was prosić o podpowiedź jak zacząć rozwiązywanie takiego zadania?
Para jedynek w sekwencji zero-jedynkowej.
Para jedynek w sekwencji zero-jedynkowej.
Ostatnio zmieniony 28 paź 2013, o 09:30 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 .
-
Naed Nitram
- Użytkownik
- Posty: 121
- Rejestracja: 8 paź 2013, o 17:08
- Płeć: Mężczyzna
- Lokalizacja: hd
- Podziękował: 2 razy
- Pomógł: 44 razy
Para jedynek w sekwencji zero-jedynkowej.
Ciągowi \(\displaystyle{ (x_n)}\) przyporządkujmy ciąg \(\displaystyle{ (y_n)}\):
\(\displaystyle{ y_1=x_1}\)
\(\displaystyle{ y_i=x_{i-1}+x_i\mod 2}\) dla \(\displaystyle{ 1<i\le n}\).
Przyporządkowanie jest wzajemnie jednoznacznym odwzorowaniem pomiędzy zbiorami ciągów zero-jedynkowych długości \(\displaystyle{ n}\). Obrazami ciągów \(\displaystyle{ (x_i)}\) bez dwóch kolejnych jedynek są ciągi, które (po utożsamieniu ciągów ze słowami nad \(\displaystyle{ \{0,1\}}\)) zaczynają się pewną liczbą zer a kończą pewną liczbą jedynek. Te z kolei łatwo zliczyć.
\(\displaystyle{ y_1=x_1}\)
\(\displaystyle{ y_i=x_{i-1}+x_i\mod 2}\) dla \(\displaystyle{ 1<i\le n}\).
Przyporządkowanie jest wzajemnie jednoznacznym odwzorowaniem pomiędzy zbiorami ciągów zero-jedynkowych długości \(\displaystyle{ n}\). Obrazami ciągów \(\displaystyle{ (x_i)}\) bez dwóch kolejnych jedynek są ciągi, które (po utożsamieniu ciągów ze słowami nad \(\displaystyle{ \{0,1\}}\)) zaczynają się pewną liczbą zer a kończą pewną liczbą jedynek. Te z kolei łatwo zliczyć.
Para jedynek w sekwencji zero-jedynkowej.
Doszedłem na piechotę do tego, że dla:
2 liczb \(\displaystyle{ P=\frac14}\),
3 liczb \(\displaystyle{ P=\frac28}\),
4 liczb \(\displaystyle{ P=\frac{5}{16}}\),
5 liczb \(\displaystyle{ P=\frac{10}{32}}\),
6 liczb \(\displaystyle{ P=\frac{20}{64}}\),
7 liczb \(\displaystyle{ P=\frac{38}{128}}\),
8 liczb \(\displaystyle{ P=\frac{71}{256}}\),
9 liczb \(\displaystyle{ P=\frac{130}{512}}\),
10 liczb \(\displaystyle{ P=\frac{235}{1024}}\),
ale w jaki sposób bym nie próbował opisać to wzorem to gdzieś się nie zgadza ;/
2 liczb \(\displaystyle{ P=\frac14}\),
3 liczb \(\displaystyle{ P=\frac28}\),
4 liczb \(\displaystyle{ P=\frac{5}{16}}\),
5 liczb \(\displaystyle{ P=\frac{10}{32}}\),
6 liczb \(\displaystyle{ P=\frac{20}{64}}\),
7 liczb \(\displaystyle{ P=\frac{38}{128}}\),
8 liczb \(\displaystyle{ P=\frac{71}{256}}\),
9 liczb \(\displaystyle{ P=\frac{130}{512}}\),
10 liczb \(\displaystyle{ P=\frac{235}{1024}}\),
ale w jaki sposób bym nie próbował opisać to wzorem to gdzieś się nie zgadza ;/
Ostatnio zmieniony 28 paź 2013, o 09:33 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
Naed Nitram
- Użytkownik
- Posty: 121
- Rejestracja: 8 paź 2013, o 17:08
- Płeć: Mężczyzna
- Lokalizacja: hd
- Podziękował: 2 razy
- Pomógł: 44 razy
Para jedynek w sekwencji zero-jedynkowej.
Moja wskazówka jest bez sensu. Inne zadanie rozwiązywałem.
Od nowa:
\(\displaystyle{ S_0(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się zerem i mających dokładnie jedną parę kolejnych jedynek
\(\displaystyle{ S_1(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się jedynką i mających dokładnie jedną parę kolejnych jedynek
\(\displaystyle{ T_0(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się zerem i nie mających par kolejnych jedynek
\(\displaystyle{ T_1(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się jedynką i nie mających par kolejnych jedynek.
Mamy wówczas:
\(\displaystyle{ T_0(n+1)=T_0(n)+T_1(n)}\)
\(\displaystyle{ T_1(n)=T_0(n-1)}\)
skąd:
\(\displaystyle{ T_0(n+1)=T_0(n)+T_0(n-1)}\)
czyli \(\displaystyle{ T_0(n)}\) to ciąg Fibonacciego:
\(\displaystyle{ T_0(n)=F_n}\), dla \(\displaystyle{ n=1,2,\ldots}\)
\(\displaystyle{ T_1(n)=F_{n-1}}\), dla \(\displaystyle{ n=1,2,\ldots}\)
Z kolei:
\(\displaystyle{ (*)S_0(n+1)=S_0(n)+S_1(n)}\)
\(\displaystyle{ (**)S_1(n+1)=S_0(n)+T_1(n)}\).
Z (*) dla \(\displaystyle{ n\ge 5}\):
\(\displaystyle{ S_0(n)=1+\sum_{i=3}^{n-1}S_0(i)}\)
skąd:
\(\displaystyle{ S_0(n)=S_0(n-1)+1+\sum_{i=3}^{n-2}S_0(i)=2S_0(n-1)}\)
i ostatecznie:
\(\displaystyle{ S_0(n)=S_0(5)\cdot 2^{n-5}=5\cdot 2^{n-5}}\)
dla \(\displaystyle{ n\ge 5}\).
Podsumowując dla \(\displaystyle{ n\ge 5}\):
\(\displaystyle{ S_0(n+1)+S_1(n+1)=S_0(n+1)+S_0(n)+T_1(n)=5\cdot 2^{n-4}+5\cdot 2^{n-5}+F_{n-1}}\).
To daje wynik dla \(\displaystyle{ n\ge 6}\):
\(\displaystyle{ \frac{5\cdot 2^{n-5}+5\cdot 2^{n-6}+F_{n-1}}{2^n}=\frac{15\cdot 2^{n-6}+F_{n-1}}{2^n}}\)
a dla mniejszych \(\displaystyle{ n}\) na piechotę sprawdzamy.
Dla pełności:
\(\displaystyle{ F_n=\frac{\left(\frac{1+\sqrt 5}2\right)^n-\left(\frac{1-\sqrt 5}2\right)^n}{\sqrt 5}}\)
co pewnie na tym forum wielokrotnie wyprowadzano.
Od nowa:
\(\displaystyle{ S_0(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się zerem i mających dokładnie jedną parę kolejnych jedynek
\(\displaystyle{ S_1(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się jedynką i mających dokładnie jedną parę kolejnych jedynek
\(\displaystyle{ T_0(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się zerem i nie mających par kolejnych jedynek
\(\displaystyle{ T_1(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) kończących się jedynką i nie mających par kolejnych jedynek.
Mamy wówczas:
\(\displaystyle{ T_0(n+1)=T_0(n)+T_1(n)}\)
\(\displaystyle{ T_1(n)=T_0(n-1)}\)
skąd:
\(\displaystyle{ T_0(n+1)=T_0(n)+T_0(n-1)}\)
czyli \(\displaystyle{ T_0(n)}\) to ciąg Fibonacciego:
\(\displaystyle{ T_0(n)=F_n}\), dla \(\displaystyle{ n=1,2,\ldots}\)
\(\displaystyle{ T_1(n)=F_{n-1}}\), dla \(\displaystyle{ n=1,2,\ldots}\)
Z kolei:
\(\displaystyle{ (*)S_0(n+1)=S_0(n)+S_1(n)}\)
\(\displaystyle{ (**)S_1(n+1)=S_0(n)+T_1(n)}\).
Z (*) dla \(\displaystyle{ n\ge 5}\):
\(\displaystyle{ S_0(n)=1+\sum_{i=3}^{n-1}S_0(i)}\)
skąd:
\(\displaystyle{ S_0(n)=S_0(n-1)+1+\sum_{i=3}^{n-2}S_0(i)=2S_0(n-1)}\)
i ostatecznie:
\(\displaystyle{ S_0(n)=S_0(5)\cdot 2^{n-5}=5\cdot 2^{n-5}}\)
dla \(\displaystyle{ n\ge 5}\).
Podsumowując dla \(\displaystyle{ n\ge 5}\):
\(\displaystyle{ S_0(n+1)+S_1(n+1)=S_0(n+1)+S_0(n)+T_1(n)=5\cdot 2^{n-4}+5\cdot 2^{n-5}+F_{n-1}}\).
To daje wynik dla \(\displaystyle{ n\ge 6}\):
\(\displaystyle{ \frac{5\cdot 2^{n-5}+5\cdot 2^{n-6}+F_{n-1}}{2^n}=\frac{15\cdot 2^{n-6}+F_{n-1}}{2^n}}\)
a dla mniejszych \(\displaystyle{ n}\) na piechotę sprawdzamy.
Dla pełności:
\(\displaystyle{ F_n=\frac{\left(\frac{1+\sqrt 5}2\right)^n-\left(\frac{1-\sqrt 5}2\right)^n}{\sqrt 5}}\)
co pewnie na tym forum wielokrotnie wyprowadzano.
Para jedynek w sekwencji zero-jedynkowej.
Strasznie dziękuję za pomoc i czas jaki poświęcasz, bo widzę, że już kilka razy to edytowałeś.
Problem tylko w tym, że to działa zaledwie dla n = 6 lub 7. Już dla 8 wyjdzie nam:
\(\displaystyle{ \frac{15 \cdot 4 + 13 }{256} = \frac{73}{256} \neq \frac{71}{256}}\)
Kolejne też nam uciekną:
\(\displaystyle{ n=9: \frac{141}{512} \neq \frac{130}{512},
n=10: \frac{274}{1024} \neq \frac{235}{1024}}\)
PS.
Przepraszam za brak/złego LaTeXa
Problem tylko w tym, że to działa zaledwie dla n = 6 lub 7. Już dla 8 wyjdzie nam:
\(\displaystyle{ \frac{15 \cdot 4 + 13 }{256} = \frac{73}{256} \neq \frac{71}{256}}\)
Kolejne też nam uciekną:
\(\displaystyle{ n=9: \frac{141}{512} \neq \frac{130}{512},
n=10: \frac{274}{1024} \neq \frac{235}{1024}}\)
PS.
Przepraszam za brak/złego LaTeXa
-
Naed Nitram
- Użytkownik
- Posty: 121
- Rejestracja: 8 paź 2013, o 17:08
- Płeć: Mężczyzna
- Lokalizacja: hd
- Podziękował: 2 razy
- Pomógł: 44 razy
Para jedynek w sekwencji zero-jedynkowej.
Mnie też wychodzi \(\displaystyle{ \frac{71}{256}}\), więc gdzieś musi być błąd.
Pewnie da się poprawić, ale potrafię uprościć rachunki. Niech \(\displaystyle{ S(n)}\) to liczba, o którą chodzi, zaś \(\displaystyle{ T(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) bez kolejnych jedynek.
Wówczas rozważając ciągi długości \(\displaystyle{ n}\) kończące się \(\displaystyle{ 0, 01, 011}\) otrzymujemy zależność:
\(\displaystyle{ S(n)=S(n-1)+S(n-2)+T(n-3)}\).
Podobnie, jak poprzednio zauważamy, że:
\(\displaystyle{ T(n)=F_{n+2}}\)
i mamy zależność rekurencyjną dla \(\displaystyle{ n\ge 2}\):
\(\displaystyle{ S(n)=S(n-1)+S(n-2)+F_{n-1}}\),
gdzie \(\displaystyle{ F_n}\) to ciąg Fibonacciego: \(\displaystyle{ (F_0=0,1,1,2,3,5,...)}\).
Przy czym \(\displaystyle{ S(0)=S(1)=0}\).
Ten ciąg daje wyniki zgodne z oczekiwaniami.
Funkcja tworząca ciągu \(\displaystyle{ S(n)}\) to kwadrat funkcji tworzącej ciągu \(\displaystyle{ F_n}\), skąd:
\(\displaystyle{ S(n)=\sum_{i+j=n}F_iF_j}\).
Nie znam się na ciągu \(\displaystyle{ F_n}\), więc nie wiem, czy to się da uprościć.
Pewnie da się poprawić, ale potrafię uprościć rachunki. Niech \(\displaystyle{ S(n)}\) to liczba, o którą chodzi, zaś \(\displaystyle{ T(n)}\) to liczba ciągów długości \(\displaystyle{ n}\) bez kolejnych jedynek.
Wówczas rozważając ciągi długości \(\displaystyle{ n}\) kończące się \(\displaystyle{ 0, 01, 011}\) otrzymujemy zależność:
\(\displaystyle{ S(n)=S(n-1)+S(n-2)+T(n-3)}\).
Podobnie, jak poprzednio zauważamy, że:
\(\displaystyle{ T(n)=F_{n+2}}\)
i mamy zależność rekurencyjną dla \(\displaystyle{ n\ge 2}\):
\(\displaystyle{ S(n)=S(n-1)+S(n-2)+F_{n-1}}\),
gdzie \(\displaystyle{ F_n}\) to ciąg Fibonacciego: \(\displaystyle{ (F_0=0,1,1,2,3,5,...)}\).
Przy czym \(\displaystyle{ S(0)=S(1)=0}\).
Ten ciąg daje wyniki zgodne z oczekiwaniami.
Funkcja tworząca ciągu \(\displaystyle{ S(n)}\) to kwadrat funkcji tworzącej ciągu \(\displaystyle{ F_n}\), skąd:
\(\displaystyle{ S(n)=\sum_{i+j=n}F_iF_j}\).
Nie znam się na ciągu \(\displaystyle{ F_n}\), więc nie wiem, czy to się da uprościć.
-
Kartezjusz
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Para jedynek w sekwencji zero-jedynkowej.
Sprawdziłem liczniki i zauważyłem, że jeśli \(\displaystyle{ S_{n}}\)to liczba szukanych ciągów długości \(\displaystyle{ n}\) to
\(\displaystyle{ S_{2}=1+0=F_{1}+0}\)
\(\displaystyle{ S_{3}=2=1+1=F_{2}+1}\)
\(\displaystyle{ S_{4}=S_{2}+S_{3}+2=S_{4}=S_{2}+S_{3}+F_{3}}\)
\(\displaystyle{ S_{5}=S_{3}+S_{4}+3=S_{5}=S_{3}+S_{4}+F_{4}}\)...
Myslę,że dla pozostałych przypadków powinno być to samo, czyli w ogólności
Jeśli \(\displaystyle{ H_{2}=0}\),\(\displaystyle{ H_{1}=1}\) oraz \(\displaystyle{ H_{n}=H_{n-1}+H_{n-2}}\)
to \(\displaystyle{ S_{n}=2F_{n-2}+H_{n-1}+H_{n-2}}\)
Ciąg \(\displaystyle{ H}\) to też ciąg podobny do Fibonacciego, tylko przesunięty w prawo.
\(\displaystyle{ S_{2}=1+0=F_{1}+0}\)
\(\displaystyle{ S_{3}=2=1+1=F_{2}+1}\)
\(\displaystyle{ S_{4}=S_{2}+S_{3}+2=S_{4}=S_{2}+S_{3}+F_{3}}\)
\(\displaystyle{ S_{5}=S_{3}+S_{4}+3=S_{5}=S_{3}+S_{4}+F_{4}}\)...
Myslę,że dla pozostałych przypadków powinno być to samo, czyli w ogólności
Jeśli \(\displaystyle{ H_{2}=0}\),\(\displaystyle{ H_{1}=1}\) oraz \(\displaystyle{ H_{n}=H_{n-1}+H_{n-2}}\)
to \(\displaystyle{ S_{n}=2F_{n-2}+H_{n-1}+H_{n-2}}\)
Ciąg \(\displaystyle{ H}\) to też ciąg podobny do Fibonacciego, tylko przesunięty w prawo.
-
Naed Nitram
- Użytkownik
- Posty: 121
- Rejestracja: 8 paź 2013, o 17:08
- Płeć: Mężczyzna
- Lokalizacja: hd
- Podziękował: 2 razy
- Pomógł: 44 razy
Para jedynek w sekwencji zero-jedynkowej.
Udało mi się zwinąć sumę:
\(\displaystyle{ \sum_{i+j=m}F_iF_j=\frac 15\cdot\left((n-1)F_n+2n\cdot F_{n-1}\right)}\)
czyli wynik to:
\(\displaystyle{ \frac{(n-1)F_n+2n\cdot F_{n-1}}{5\cdot 2^n}}\)
dla \(\displaystyle{ n\ge 1}\).
\(\displaystyle{ \sum_{i+j=m}F_iF_j=\frac 15\cdot\left((n-1)F_n+2n\cdot F_{n-1}\right)}\)
czyli wynik to:
\(\displaystyle{ \frac{(n-1)F_n+2n\cdot F_{n-1}}{5\cdot 2^n}}\)
dla \(\displaystyle{ n\ge 1}\).
Para jedynek w sekwencji zero-jedynkowej.
Najmocniej dziękuję I strasznie mi głupio, że tylko tyle. Szczególnie, że domyślam się ile się nad tym głowiłeś, a na pewno widziałem wielokrotnie modyfikowane posty. Bardzo dziękuję!
-
Naed Nitram
- Użytkownik
- Posty: 121
- Rejestracja: 8 paź 2013, o 17:08
- Płeć: Mężczyzna
- Lokalizacja: hd
- Podziękował: 2 razy
- Pomógł: 44 razy
Para jedynek w sekwencji zero-jedynkowej.
Wielokrotna modyfikacja to rezultat przypadkowego klikania "Wyślij" zamiast "Podgląd", czyli notorycznego wysyłania brudnopisów. Na ogół piszę po ciemku i/lub leżąc. Ale to mój problem.
Nauczyłem się czegoś nowego, więc również dziękuję.
Nauczyłem się czegoś nowego, więc również dziękuję.