Determine o número de modos de cobrir um tabuleiro 2 \times n com dominós 2 \times 1 iguais.

Passo 1

O enunciado pede para contar de quantas formas podemos cobrir um tabuleiro de 2\times n usando apenas dominós de tamanho 2\times1. Esse é um problema clássico de contagem de tilings que leva a uma recorrência de Fibonacci.

Passo 2

Definimos a_n como o número de maneiras de cobrir um tabuleiro de 2\times n. Nosso objetivo é achar uma fórmula ou recorrência para a_n.

Passo 3

Considere as possibilidades de cobertura envolvendo a primeira coluna (mais à esquerda) do tabuleiro de 2\times n:
  1. Podemos colocar um dominó vertical ocupando toda a primeira coluna. Nesse caso, o restante a cobrir é um tabuleiro 2\times(n-1), que pode ser feito de a_{n-1} formas.
  2. Podemos colocar dois dominós horizontais empilhados, ocupando as duas células da primeira e da segunda coluna. Nesse caso, sobra um tabuleiro 2\times(n-2), que pode ser coberto de a_{n-2} maneiras.

Passo 4

Somando essas duas possibilidades, obtemos a relação de recorrência
a_n = a_{n-1} + a_{n-2}.

Passo 5

Agora precisamos das condições iniciais. Para n=0 (tabuleiro vazio) há exatamente uma forma de “cobrir” (não colocar nada), ou seja,
a_0 = 1.
Para n=1 (um tabuleiro 2\times1) só cabe um dominó vertical, logo
a_1 = 1.

Passo 6

A sequência (a_n) satisfaz
a_0=1,\quad a_1=1,\quad a_n=a_{n-1}+a_{n-2}.
Isso é exatamente a definição dos números de Fibonacci deslocados, de modo que
a_n = F_{n+1},
onde (F_k) é a sequência de Fibonacci usual com F_1=1, F_2=1. Em forma fechada temos também
a_n = \frac{1}{\sqrt{5}}\Bigl(\bigl(\tfrac{1+\sqrt5}{2}\bigr)^{\,n+1} - \bigl(\tfrac{1-\sqrt5}{2}\bigr)^{\,n+1}\Bigr).

Resposta

O número de modos de cobrir um tabuleiro 2\times n com dominós 2\times1 é
\boxed{a_n = F_{n+1}},
sendo F_{n+1} o (n+1)-ésimo número de Fibonacci.

Exercícios relacionados