logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 5478

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

mateusz3338
postów: 2
2017-06-02 20:10:15

Dla każdej liczby naturalnej n niech a_n oznacza liczbę ciągów ternarnych (tj. o wyrazach 0,1,2) długości n, w których każde dwa symbole niezerowe są rozdzielone przynajmniej jednym zerem. Znajdź rekurencję dla ciągu a_n.


tumor
postów: 8070
2017-06-09 09:36:12

$a_1=1+2=3$ (jeden ciąg kończy się 0, dwa ciągi liczbą różną od 0)

Zauważmy teraz, że każdy ciąg z powyższych możemy przedłużyć liczbą 0, a tylko jeden ciąg liczbą różną od zera (na 2 sposoby), czyli
$a_2=a_1*1+1*2$

Wobec tego teraz $a_1$ ciągów kończy się na 0 (i możemy je przedłużyć liczbą inną niż 0), a wszystkie ciągi możemy przedłużyć wyrazem 0

$a_3=2a_1+a_2$

ogólnie:
rozpatrując ciągi o długości n+2 widzimy, że każdy ciąg o długości n+1 możemy przedłużyć zerem, natomiast tylko te ciągi możemy przedłużyć liczbą 1 lub 2, które były przedłużone zerem krok wcześniej. Stąd
$a_{n+2}=a_{n+1}+2a_n$ dla n>0





strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj