Re: [obm-l] Tabuleiro 3 x 2n com dominos 2x1

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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
=========================================================================