szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 25 lis 2017, o 18:27 
Użytkownik

Posty: 6
Lokalizacja: Warszawa
Ile można utworzyć ciągów długości n złożonych z cyfr 0,1 i 2 tak, by żadne dwie jedynki ani żadne dwie dwójki nie stały obok siebie?
Zadanie należy rozwiązać za pomocą wzoru rekurencyjnego na n-ty wyraz ciągu.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 18:57 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
Powiedzmy, że mamy ciąg długości n spełniający warunki zadania. Jeśli kończy się on jedynką bądź dwójką, to mamy dwie możliwości: albo dopisujemy dwójkę (odpowiednio: jedynkę), albo zero, by stworzyć ciąg o n+1 elementach spełniający warunki zadania. Jeśli natomiast ciąg długości n, w którym żadne dwie jedynki ani dwójki nie stoją obok siebie, kończy się zerem, to na n+1. pozycji możemy wstawić cokolwiek i dalej będzie dobrze.
Oznaczmy przez a_n liczbę wszystkich dobrych ciągów długości n, zaś przez b_n liczbę ciągów długości n kończących się zerem i spełniających warunki zadania. Mamy więc
a_{n+1}=2(a_n-b_n)+3b_n=2a_n+b_n
Z drugiej strony ciąg spełniający warunki zadania i kończący się zerem mający przy tym długość n+1 możemy zbudować tak: do każdego ciągu długości n spełniającego warunki zadania dopisujemy po prostu zero (inaczej zrobić nie można, bo jeśli gdzieś wcześniej stały obok siebie jedynki bądź dwójki, to po dopisaniu zera na końcu oczywiście to się nie zmieni).
Czyli b_{n+1}=a_n
Zatem a_{n+1}=2a_n+b_n=2a_n+a_{n-1}

i mamy proste równanie jednorodne. Dopisz sobie a_1=3, a_2=7 (policzyłem na palcach) i rozwiązujesz to ulubioną metodą.
Góra
Kobieta Offline
PostNapisane: 25 lis 2017, o 19:09 
Użytkownik

Posty: 6
Lokalizacja: Warszawa
Dzięki :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiazywanie rownania z uzyciem wzoru Newtona  birdy1986  7
 m dyskretna - Ile jest całkowitych rozwiązań równania .  torbol  1
 Równanie rekurencyjne liniowe niejednorodne  freeze2  1
 Kombinatoryka (rozwiąż równania)  allexx  3
 Jak kombinatorycznie dowieść poprawność równania??  tupatek  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl