Znajdź zależność rekurencyjną RasGrass: Niech a_n będzie liczbą słów długości n składających się z liter {a,b,c} bez dwóch kolejnych liter a. Znajdź zależność rekurencyjną na a_n Zrobiłem to rozbijając problem na 3 przypadki: 1. Na ostatnim miejscu jest a − wtedy miejsc na literę a mamy n−2 2. Na ostatnim miejscu jest b − wtedy miejsc na literę a mamy n−1 3. Na ostatnim miejscu jest c − wtedy miejsc na literę a mamy n−1 Zatem a_n=2a_n−1+a_n−2 ale wypisując wszystkie możliwośc dla n=1, n=2 i n=3 ten wzór mi się nie zgadaza. Czy mógłby mi ktoś wytłumaczyć co robię źle?

RasGrass: Dodam, że wypisując wszystkie przypadki wyszło mi: dla n=1 − 3 dla n=2 − 8 więc zgodnie ze wzorem dla n=3 powinno wyjść 19, a wypisując wszystko wychodzi 20.

RasGrass: Dobra, chyba do tego doszedłem − może się komuś przyda: Należy spojrzeć nie na ostatnie miejsce, lecz na przedostatnie. Jeżeli na przedostatnim miejscu będzie litera b, to literę a będziemy mogli postawić n−1 miejscach (bo 1 miejsce zajmuje b). Tak samo jak na przedostatnim miejscu mamy c. Jeżeli jednak na przedostatnim miejscu jest a − to wtedy: nie będziemy mogli postawić litery a na n−2 miejscach − tam gdzie jest litera a oraz na ostatnim miejscu, a takze na kolejnych n−2 miejscach − tam gdzie jest a i na miejscu przed litera a. 1. przypadek ~ ~ ~ ~ b ~ − nie możemy postawić a tylko na miejscu w którym jest b − czyli mamy do dyspozycji n−1 miejsc 2. przypadek ~ ~ ~ ~ c ~ − j.w. 3.1 przypadek ~ ~ ~ ~ a x − nie możemy postawić litery a na miejscu wpisanej juz litery a oraz na x, czyli do dyspozycji mamy n−2 miejsc 3.2 przypadek ~ ~ ~ x a ~ − nie możemy postawić litery a na miejscu wpisanej juz litery a oraz na x, czyli do dyspozycji mamy n−2 miejsc Razem wychodzi a_n=2a_n−1*2a_n−2, a warunki początkowe to a₁=3, a₂=8.

RasGrass: a dla n=3 wychodzą oczywiście 22 wyrazy , nie 20 (mój błąd): acc, bcb, abb, cca, bba, acb, bca, aba, cbb, bbc, bab, ccc, bcc, cba, ccb, bbb, abc, cac, cab, bac, cbc, aca.