De quantas maneiras um tabuleiro retangular de damas 2 \times n pode ser ladrilhado, usando peças de 1 \times 2 e 2 \times 2 ?

Passo 1

O problema pede para contar de quantas formas podemos ladrilhar um tabuleiro de dimensão 2\times n usando peças de dimensão 1\times2 (domino, que pode ser girado para ocupar 2\times1) e quadrados 2\times2.
Conteúdo: recorrência em combinações de tilings. Vamos identificar como o lado esquerdo do tabuleiro pode ser coberto e, a partir daí, montar uma relação de recorrência para o número de tilings a_n.

Passo 2

Analisamos como preencher as primeiras colunas do tabuleiro 2\times n:
  1. Se colocamos um dominó vertical ocupando toda a coluna 1, sobra um tabuleiro 2\times(n-1).
  2. Se colocamos dois dominos horizontais empilhados nas colunas 1 e 2, sobra um tabuleiro 2\times(n-2).
  3. Se colocamos um quadrado 2\times2 nas colunas 1 e 2, também sobra um tabuleiro 2\times(n-2).

Passo 3

Da análise acima segue a recorrência
a_n \;=\; a_{n-1}\;+\;2\,a_{n-2}
com condições iniciais:
a_0 = 1\quad(\text{tabuleiro vazio}), \qquad a_1 = 1\quad(\text{apenas um dominó vertical}).ó

Passo 4

Para resolver \,a_n = a_{n-1} + 2a_{n-2}\), montamos a equação característica \[r^2 - r - 2 = 0
que tem raízes r_1 = 2 e r_2 = -1.
Logo, a solução geral é
a_n = A\cdot 2^n + B\cdot(-1)^n.
Usando a_0=1 e a_1=1, obtemos
\begin{cases} A + B = 1,\\\\ 2A - B = 1, \end{cases}
cuja solução é A=\tfrac{2}{3}\] e \(B=\tfrac{1}{3}. Portanto
a_n = \frac{2}{3}\,2^n + \frac{1}{3}(-1)^n = \frac{2^{n+1} + (-1)^n}{3}.

Resposta

a_n = \frac{2^{n+1} + (-1)^n}{3}.

Exercícios de Livros Relacionados