szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 wrz 2005, o 23:59 
Użytkownik

Posty: 3
Lokalizacja: Toruń
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ć?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 17 wrz 2005, o 11:03 
Gość Specjalny

Posty: 534
Lokalizacja: Warszawa
niech D_n oznacza taki podzial dla prostokata o wymiarach 2xn
chcemy obliczyc 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 D_{n+1}=2D_n+3D_{n-1}+2D_{n-2}+2D_{n-3}+...+2D_1+2D_0
tamta trojka przy D_{n-1} to nie przypadek w tym przypadku mamy trzy mozliwosci ulozenia przodu
zeby zwiazek byl zalezny od kilku wczesniejszych robimy tak
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}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wzór An - rekurencja  robix  4
 rekurencja drzewa  Liar  0
 Rekurencja liniowa I rzędu - pilny problem, raczej ogólny  PolGraphic  4
 Rekurencja i inne  grobath  1
 Podział zbioru na cykle.  Richard del Ferro  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl