[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Domino

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.