Witam,
mam takie oto zadanie:
Dany jest alfabet \(\displaystyle{ A=\{x,y,z\}}\). Podaj wzór rekurencyjny na liczbę słów \(\displaystyle{ t_n}\) długości \(\displaystyle{ n}\) utworzonych z alfabetu \(\displaystyle{ A}\), które zawierają parzystą liczbę liter \(\displaystyle{ z}\). Zamień wzór rekurencyjny na wzór jawny oraz wykaż, że wzór jawny jest poprawny.
No to ja założyłem, że jeżeli w danym ciągu jest \(\displaystyle{ 0}\) liter \(\displaystyle{ z}\) to jest to parzysta liczba \(\displaystyle{ z}\), bo \(\displaystyle{ 0}\) jest parzyste, więc wziąłem również pod uwagę wyrazy, które tegoż 'z' nie zawierają. Przy policzeniu ilości ciągów dla \(\displaystyle{ n=1, n=2}\) oraz \(\displaystyle{ n=3}\) zauważyłem taką zależność, że wzór rekurencyjny wyszedł mi tak:
\(\displaystyle{ a_{n}=2a_{n-1}+2a_{n-2}}\)
Czy to poprawny tok rozumowania oraz równanie?
Podaj wzór rekurencyjny i wyznacz wzór jawny
Podaj wzór rekurencyjny i wyznacz wzór jawny
Ostatnio zmieniony 5 wrz 2018, o 16:45 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Podaj wzór rekurencyjny i wyznacz wzór jawny
Żaden tok rozumowania się nie pojawił, równanie również nie wygląda na poprawne.Czy to poprawny tok rozumowania oraz równanie?
Weź słowo długości \(\displaystyle{ n}\), jeśli kończy się na \(\displaystyle{ x \vee y}\), to po obcięciu ostatniej literki dostajesz element \(\displaystyle{ a_{n-1}}\) - czyli łącznie takich ciągów długości n nie kończących się na z masz \(\displaystyle{ 2a_{n-1}}\). Co natomiast dzieje się, gdy ciąg kończy się na z?
-
- Użytkownik
- Posty: 22211
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Podaj wzór rekurencyjny i wyznacz wzór jawny
A może tak: Niech \(\displaystyle{ a_n}\) oznacza ilość słów długości \(\displaystyle{ n}\) z parzystą ilościa \(\displaystyle{ z}\)-tów, a \(\displaystyle{ b_n}\) z nieparzystą.
Oczywiście \(\displaystyle{ a_n+b_n=???}\)
Teraz zastanów się jak powstają słowa długości \(\displaystyle{ n+1}\) za słów długości \(\displaystyle{ n}\)?
Oczywiście \(\displaystyle{ a_n+b_n=???}\)
Teraz zastanów się jak powstają słowa długości \(\displaystyle{ n+1}\) za słów długości \(\displaystyle{ n}\)?
Podaj wzór rekurencyjny i wyznacz wzór jawny
Powstają w ten sposób, że dodaję do każdego po x oraz y, bo nic to nie zmienia oraz dodaję "z" tylko tam gdzie ilość "z" jest nieparzysta?a4karo pisze:A może tak: Niech \(\displaystyle{ a_n}\) oznacza ilość słów długości \(\displaystyle{ n}\) z parzystą ilościa \(\displaystyle{ z}\)-tów, a \(\displaystyle{ b_n}\) z nieparzystą.
Oczywiście \(\displaystyle{ a_n+b_n=???}\)
Teraz zastanów się jak powstają słowa długości \(\displaystyle{ n+1}\) za słów długości \(\displaystyle{ n}\)?
Zakładając, że jeżeli ciąg ma z w sobie to jest ich parzysta liczba, bo inaczej nie mógłbym ich brać pod uwagę (chyba). Wówczas dodanie 'z' sprawia, że dany ciąg nie spełnia warunków. Dodanie x,y sprawia, że jest ok.leg14 pisze:Żaden tok rozumowania się nie pojawił, równanie również nie wygląda na poprawne.Czy to poprawny tok rozumowania oraz równanie?
Weź słowo długości \(\displaystyle{ n}\), jeśli kończy się na \(\displaystyle{ x \vee y}\), to po obcięciu ostatniej literki dostajesz element \(\displaystyle{ a_{n-1}}\) - czyli łącznie takich ciągów długości n nie kończących się na z masz \(\displaystyle{ 2a_{n-1}}\). Co natomiast dzieje się, gdy ciąg kończy się na z?
W zadaniu nie pisze nic o tym, aby nie mogły.Euler41 pisze:Czy litery \(\displaystyle{ x, y}\) mogą się powtarzać?