On Tue, Oct 07, 2003 at 09:25:29AM -0200, Claudio Buffara wrote: > Oi, Nicolau: > > Eu calculei o no. de maneiras de se cobrir um tabuleiro 3 x 2n com dominos > 2x1 e achei a recorrencia: > > f(n) = 3*f(n-1) + g(n-1) > g(n) = 2*f(n-1) + g(n-1) > > f(1) = 3, g(1) = 2 > > onde f(n) = no. desejado e g(n) = no. de maneiras de se chegar a casa 2n com > 2 dominos deitados. > > Eliminando g(n): f(n) = 4*f(n-1) - f(n-2); f(1) = 3; f(2) = 11. > > f(n) = 3, 11, 41, 153, 571, 2131, ... > > Resolvendo eu achei a formula explicita para f(n): > f(n) = (1/6)*[(3+raiz(3))*(2+raiz(3))^n + (3-raiz(3))*(2-raiz(3))^n] > > Minha duvida: Existe alguma razao para os autovalores (2+ou-raiz(3)) serem > os mesmos que no caso do pilar ou foi soh coincidencia?
Uma �tima pergunta... fico devendo. > Qual o papel (ou interpretacao) dos autovalores nesse tipo de problema? O maior autovalor d� a ordem de crescimento da fun��o. O segundo maior d� a ordem do erro da aproxima��o pelo maior e assim por diante. Bom, existem outras interpreta��es mais sutis... Acho que voc� realmente deveria tamb�m pensar na f�rmula de Kasteleyn... []s, N. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
