Liczba słów określonej długości - rekurencja

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
zedd5
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 12 mar 2008, o 00:51
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy
Pomógł: 1 raz

Liczba słów określonej długości - rekurencja

Post autor: zedd5 »

Mam pytanie do poniższego zadania, podpunkt (b)

Zad. (Matematyka Dyskretna, Ross, paragraf 4.3., zad. 7.)
Niech:
\(\displaystyle{ \Sigma= \{a, b, c\}}\) (sigma oznacza alfabet)
i niech \(\displaystyle{ s_{n}}\) oznacza liczbę słów o długości n, które nie mają kolejnych liter a.
(a) Oblicz \(\displaystyle{ s_{0},s_{1},s_{2}}\).
(b) Znajdź wzór rekurencyjny na \(\displaystyle{ s_{n}}\).
(c) Oblicz \(\displaystyle{ s_{3},s_{4}}\).

Rozwiązanie:
\(\displaystyle{ A_{n}}\) oznacza zbiór słów o długości n spełniający kryteria.
(a)
\(\displaystyle{ A_{0}=\{\lambda\},\qquad s_{0}=1}\)
\(\displaystyle{ A_{1}=\Sigma,\qquad s_{1}=3}\)
\(\displaystyle{ A_{2}=\Sigma^{2}\backslash\{aa\},\qquad s_{2}=3^{2}-1=8}\)

(b)
Jeżeli słowo (n) kończy się na b lub c, możliwe jest dowolne zakończenie wcześniejszego (n-1) słowa. Natomiast, gdy słowo jest zakończone na a, wcześniejsze słowo musi być zakończone na b lub c .
Z powyższego wynika, że (taka odpowiedź pasuje do odpowiedzi):
\(\displaystyle{ s_{n}=2s_{n-1}+2s_{n-2}}\)

I tutaj pojawia się moje pytanie:
Dlaczego nie może to być równanie takie:
\(\displaystyle{ s_{n}=2s_{n-1}+\frac{2}{3}s_{n-1}}\)
Uzasadniam to tym, że 2/3 słów kończy się na b lub c, a 1/3 na a. Wyjaśnijcie mi, gdzie robię błąd.

(c)
Ze wzoru rekurencyjnego:
\(\displaystyle{ s_{3}=22, s_{4}=60}\)
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Liczba słów określonej długości - rekurencja

Post autor: »

zedd5 pisze: I tutaj pojawia się moje pytanie:
Dlaczego nie może to być równanie takie:
\(\displaystyle{ s_{n}=2s_{n-1}+\frac{2}{3}s_{n-1}}\)
Uzasadniam to tym, że 2/3 słów kończy się na b lub c, a 1/3 na a. Wyjaśnijcie mi, gdzie robię błąd.
Ale te dwie trzecie to z ogólnej liczby słów, a nie z \(\displaystyle{ s_{n-1}}\) - no i w tej ogólnej liczbie słów są też złe, więc taką drogą do niczego nie dojdziemy.

Q.
zedd5
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 12 mar 2008, o 00:51
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy
Pomógł: 1 raz

Liczba słów określonej długości - rekurencja

Post autor: zedd5 »

Qń, dzięki za odpowiedź. Byłem na wakacjach i nie mogłem odpisać.

Mógłbyś jednak bardziej uzasadnić swoje stanowisko?

Bo ja biorę dokładnie 2/3, ale jak ze wzoru wynika z \(\displaystyle{ s_{n-1}}\) słów, a nie z całości, czyli z \(\displaystyle{ s_{n}}\) słów.
A te 2/3 wziąłem, żeby nie dobierać "złych" słów. Gdyby moje rozwiązanie zawierało złe słowa, byłoby ich więcej, a otrzymuje ich mniej (zobacz wyniki programu dla różnych n, poniżej):

Rozwiązania rekurencji: pierwsza liczba - wartość n, druga liczba - wartość rekurencji dla n > 1: s(n)=2*s(n-1)+2*s(n-2), trzecia liczba - wartość rekurencji dla n > 0: s(n)=sufit(8/3*s(n-1)). Wziąłem już nawet funkcję sufit, żeby wynik zaokrąglić do góry.

0: 1 1
1: 3 3
2: 8 8
3: 22 22
4: 60 59
5: 164 158
6: 448 422
7: 1224 1126
8: 3344 3003
9: 9136 8008
10: 24960 21355
11: 68192 56947
12: 186304 151859
13: 508992 404958
14: 1390592 1079888
15: 3799168 2879702
16: 10379520 7679206
17: 28357376 20477883
18: 77473792 54607688
19: 211662336 145620502
Wredootka
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 16 kwie 2009, o 18:48
Płeć: Kobieta

Liczba słów określonej długości - rekurencja

Post autor: Wredootka »

Skąd ta lambda?w a0?
ODPOWIEDZ