rekurencja - podział prostokąta

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
nova
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 wrz 2005, o 09:59
Płeć: Mężczyzna
Lokalizacja: Toruń

rekurencja - podział prostokąta

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

Znaleźć wzór rekurencyjny a(n) wskazujący ilość możliwych podziałów prostokąta o wymiarach 2 x n na prostokąty 1 x 2 i 1 x 1.

Ma ktoś jakiś pomysł, jak to rozwiązać?

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

rekurencja - podział prostokąta

Post autor: półpasiec » 17 wrz 2005, o 11:03

niech \(\displaystyle{ D_n}\) oznacza taki podzial dla prostokata o wymiarach 2xn
chcemy obliczyc \(\displaystyle{ D_{n+1}}\)
mozemy na ostatni prostokat polozyc klocki na dwa sposoby
mozemy jednak polozyc klocek 2x1 poziomo, bedziemy zliczac takie ustawienia ze ostatnie klocki sa polozone poziomo, az nie dojdziemy do prostokata o mniejszych rozmiarach
widac ze ten przod mozemy na dwa sposoby ustawic- 1x1 na gorze albo dole
widac wiec ze \(\displaystyle{ D_{n+1}=2D_n+3D_{n-1}+2D_{n-2}+2D_{n-3}+...+2D_1+2D_0}\)
tamta trojka przy \(\displaystyle{ D_{n-1}}\) to nie przypadek w tym przypadku mamy trzy mozliwosci ulozenia przodu
zeby zwiazek byl zalezny od kilku wczesniejszych robimy tak
\(\displaystyle{ D_{n+1}= 2D_n+3D_{n-1}+2D_{n-2}+2D_{n-3}+...+2D_1+2D_0= \\ =
2D_n+D_{n-1}-D_{n-2}+2D_{n-1}+3D_{n-2}+2D_{n-3}+...+2D_1+2D_0= \\ =
2D_n+D_{n-1}-D_{n-2}+D_n=3D_n+D_{n-1}-D_{n-2}}\)

ODPOWIEDZ