Matematyka.pl

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}\)

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.

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

Skąd ta lambda?w a0?