szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 lis 2014, o 21:53 
Użytkownik

Posty: 2
Lokalizacja: Warszawa
Mam takie dwa zadanka:

1. Na ile sposobów można wytworzyć ciąg długości n z liczb 0,1,2 tak aby żadne dwie jedynki nie stały obok siebie.
2. Na ile sposobów można wytworzyć ciąg długości n z liczb 0,1,2 tak aby żadne dwie jedynki oraz żadne dwie dwójki nie stały obok siebie.

Przyjąłem takie rozumowanie rekurencyjne:

a_{0} = 1, a_{1} = 3
Dla n=2
1. Jeśli na pierwszym miejscu mamy 0, to po 0 mogą być 3 cyfry, czyli an-1. Analogicznie sytuacja zachodzi dla 2, więc mamy a_{n-1} x 2. Gdy na pierwszym miejscu mamy 1 zachodzi sytuacja wyjątkowa, żeby warunek nam się dopełnił musimy zużyć jeszcze jeden element, żeby wykluczyć pojawienie się 1. Stąd n-2, bo musimy tam wsadzić jeszcze jedną cyfrę. Mamy więc 2 przypadki 10 oraz 12, w każdym z nich jest 1 możliwość na umieszczenie 0 oraz 2, więc a_{n-2}. Generalnie wynik zgadza się z wypisywaniem sobie poszczególnych wyrazów dla n=3 i dalej pewnie też.
Mamy ogółem a_{n} = 2*a_{n-1} + 2*a_{n-2}

2. Jeśli na pierwszym miejscu mamy 0, to po 0 mamy 3 opcje, czyli a_{n-1}.
Jeśli na pierwszym miejscu mamy 1 musimy postąpić tak jak poprzednio - wsadzić 2 lub 0, co daje nam dwa przypadki i n-2. I tak samo musimy postąpić dla 2, stąd w sumie n-2 x 4.
Wychodzi niby a_{n} = a_{n-1} + 4*a_{n-2}

No tylko problem w tym, że ten drugi wzór mi się nie zgadza z tym co wypisuję sobie na kartce jako wyrazy dla n=3. Wzór podaje 19 możliwości, zaś z wypisywania mam 17 jeśli czegoś nie pominąłem.

Gdzie jest błąd w rozumowaniu i jak go naprawić?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2014, o 01:21 
Użytkownik
Avatar użytkownika

Posty: 1227
Ojejku, dlaczego rekurencyjnie? Poustawiaj sobie najpierw dwójki i trójki, a potem między nie "powtykaj" jedynki. Możesz w ciągu mieć do 0 do k jedynek (właśnie wróciłem z imprezy - nie policzę). I w zależności od tego będziesz miał m dwójek i n-m-k trójek. Ostatecznie, jak to rozpiszesz, dostaniesz podwójną sumę (po k, n) z jakimiśtam symbolami Newtona. Rąbnij sobie funkcję tworzącą, wylicz i masz.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2014, o 13:07 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Hm twoja propozycja jest bardzo skomplikowana! Nawet przed imprezą bym jej nie rozkminił.
Ja jestem prosty i prosto myślę więc:
Moja propozycja do b). to:

a_{1}=3

a_{3}=7

a_{n+2}=2a_{n+1}+a_{n}


Bo to proste wszystko przemnażasz przez dwa i dodajesz jeszcze te wcześniejsze gdzie na początku są zera. Bo co by nie stało na końcu to i tak w najgorszym przypadku możesz dopisać dwie możliwości.
A Tobie nie wychodziło bo liczyłeś pewne przypadki podwójnie!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z rekurencją  dos_  3
 problem z rekurencją - zadanie 2  marchwiak5  2
 Wzór An - rekurencja  robix  4
 Problem rozmienienia n-kwoty bez funkcji tworzących  guziaster  0
 Rekurencja - ciągi ternarne - zadanie 2  Ola_kg  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl