De quantas formas diferentes podemos cobrir um tabuleiro de 2 times n com peças de dominós que cobrem exatamente duas casas do tabuleiro?

Passo 1

O problema pede: “De quantas formas diferentes podemos cobrir um tabuleiro de usando peças de dominó ?”
Conteúdo: isso é um clássico de contagem e recorrência (também envolve a sequência de Fibonacci).
Para resolver, vamos precisar:
  1. Definir a quantidade de maneiras como uma função .
  2. Encontrar os casos base (pequenos ).
  3. Ver por que aparece uma relação de recorrência .
  4. Identificar essa recorrência como Fibonacci e, se quisermos, dar a fórmula fechada.

Passo 2

Definição e casos base.
Seja T(0) = 1 = número de maneiras de cobrir o tabuleiro T(1) = 1 .
  • Para (tabuleiro vazio) só há 1 jeito (não colocar nada):
  • Para (duas células uma em cima da outra) só cabe um dominó na vertical:

Passo 3

Montando a recorrência.
Olha o que acontece no lado esquerdo do tabuleiro T(n) = T(n-1) + T(n-2) :
  1. Se a primeira peça for vertical, ela ocupa as duas células da coluna 1, sobrando um tabuleiro . São jeitos de completar o resto.
  2. Se a primeira peça for um par de dominós horizontais, um na linha de cima e outro embaixo, eles ocupam as colunas 1 e 2. Sobra um tabuleiro , que pode ser preenchido de maneiras.
Somando as opções:

Passo 4

Reconhecendo a sequência de Fibonacci.
Aquela relação
T(n) = T(n-1) + T(n-2), T(0)=1,;T(1)=1
é exatamente a definição da sequência de Fibonacci deslocada. Se T(n) = Fn+1 é a sequência clássica com , , então dá para mostrar que
Por exemplo:
  • e .
  • e .

Passo 5

Fórmula fechada (opcional).
A fórmula de Binet para Fibonacci é
Fk = phi^k - psi^kraiz5, phi = 1+raiz52,; psi = 1-raiz52
Logo
T(n) = Fn+1 = phi^,n+1 - psi^,n+1raiz5

Resposta

O número de maneiras de cobrir um tabuleiro boxedT(n)=Fn+1 com dominós é
onde é o -ésimo número de Fibonacci (ou, em forma fechada, ).

Exercícios relacionados