Re: Domino

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

On Sun, Dec 30, 2001 at 09:58:23PM -0200, gfujiwara wrote:
> Eu estava fazendo o problema (c), e precisei de um resultado conhecido ( que
> eu desconhe�o, isto � uma pergunta).  Como � a generaliza��o de Fibonnacci
> para contar o n�mero de maneiras de preencher um tabuleiro  retangular com
> domin�s ?

Chamemos N(n,m) o n�mero de maneiras de cobrir um ret�ngulo com domin�s.
Temos N(n,2) = Fibo(n+1) (onde Fibo(0) = 0, Fibo(1) = 1 e
Fibo(n+1) = Fibo(n) + Fibo(n-1)) mas acho um pouco puxado chamar N(n,m)
de uma generaliza��o de Fibo.

Em todo caso, h� v�rias f�rmulas conhecidas para N(n,m). Uma delas �

(N(n,m))^4 = Prod_{1 <= j <= m, 1 <= k <= n} F(j/(m+1), k/(n+1))

onde 

F(x,y) = 4 + 2 cos(2 Pi x) + 2 cos(2 Pi y)

Voc� pode achar mais coisa nos artigos na minha home page e nas refer�ncias.
[]s, N.