ciągi binarne a rekurencja

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Jacek P.

ciągi binarne a rekurencja

Post autor: Jacek P. » 16 wrz 2005, o 09:46

Mam problem ze znajdowaniem funkcji rekurencyjnych dla problemów kombinatorycznych. Ostatnio "zaciąłem się" na czymś takim:

Niech p(n) oznacza ilosc ciagów binarnych dł. n, które nie zawierają 3 jedynek na sąsiednich miejscach. Znaleźć wzór rekurencyjny p(n).

Jeżeli byłoby, że nie moze być 2 jedynek, to problem byłby wręcz banalny (p(n) = p(n-1) + p(n-2) o ile się nie mylę)...

Kolejnym podobnym zadaniem jest takie, w którym w warunku zamiast 3 jedynek mamy "ilosc jedynek w ciągu jest podzielna przez 4" - z tym też mam duże kłopoty.

Byłbym wdzięczny za wszelką pomoc.

półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

ciągi binarne a rekurencja

Post autor: półpasiec » 16 wrz 2005, o 16:23

to z trzema kolejnymi jedynkami zrobilbym tak
niech \(\displaystyle{ p(n)}\) oznacza ilosc takich ciagow dlugosci \(\displaystyle{ n}\), niech tez
\(\displaystyle{ p_0(n)}\) to ilosc takich ciagow ale przy tym na pierwszych dwu pozycjach nie wystepuja jedynki, \(\displaystyle{ p_1(n)}\) na pierwszych dwu wystepuje jedna jedynka, \(\displaystyle{ p_2(n)}\) na pierwszych dwu wystepuja dwie jedynki
no to \(\displaystyle{ p_0(n)+p_1(n)+p_2(n)=p(n)}\)
teraz widac ze \(\displaystyle{ p(n+1)=2p_0(n)+2p_1(n)+p_2(n)}\)
bo jak na pierwszych dwu nie bylo dwu jedynek to mozemy na pierwsza pozycje dac dwie liczby, a jak pierwsze dwie to jedynki to mozemy tylko dac 0
zatem \(\displaystyle{ p(n+1)=2p(n)-p_2(n)}\)
wystarczy obliczyc \(\displaystyle{ p_2(n)}\), jego przod musi wygladac tak \(\displaystyle{ 110...}\)
wiec piersze trzy pozycje sa obstawione a na wczesniejsze \(\displaystyle{ n-3}\) pozycji mozemy ustawic je dowolnie, byle poprawnie wiec na \(\displaystyle{ p(n-3)}\) sposobow
zatem \(\displaystyle{ p_2(n)=p(n-3)}\)
zatem \(\displaystyle{ p(n+1)=2p(n)-p(n-3)}\)

mozna dalej sie pobawic z \(\displaystyle{ p_i}\) i dostac cos podobnego do \(\displaystyle{ p_2(n)=p(n-3)}\) i moze uzyska sie zwiazek zalezny od trzech kolejnych a nie taki z przerwa 3

nova
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 wrz 2005, o 09:59
Płeć: Mężczyzna
Lokalizacja: Toruń

ciągi binarne a rekurencja

Post autor: nova » 16 wrz 2005, o 17:33

Tak na szybko policzyłem ręcznie ilość dozwolonych kombinacji dla kilku pierwszych długości i wyszło mi coś takiego:

p(1) = 2
p(2) = 4
p(3) = 7
p(4) = 14
p(5) = 29
p(6) = 60

I nie zgadzają się te wartości z przedstawioną rekurencją. Albo ja coś źle licze, albo jest jakiś błąd.

półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

ciągi binarne a rekurencja

Post autor: półpasiec » 16 wrz 2005, o 22:24

zle liczysz

nova
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 wrz 2005, o 09:59
Płeć: Mężczyzna
Lokalizacja: Toruń

ciągi binarne a rekurencja

Post autor: nova » 16 wrz 2005, o 23:26

Fakt, mój błąd.

Nie wziąłem pod uwagę wielu ciągów, które spełniają warunki zadania. Jak wszystko dokładnie podliczyłem, to się zgadza.

ODPOWIEDZ