De quantas maneiras um tabuleiro retangular de damas
pode ser ladrilhado, usando peças de
e
?
Passo 1
O problema pede para contar de quantas formas podemos ladrilhar um tabuleiro de dimensão
usando peças de dimensão
(domino, que pode ser girado para ocupar
) e quadrados
.
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 .
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
Passo 2
Analisamos como preencher as primeiras colunas do tabuleiro
:
- Se colocamos um dominó vertical ocupando toda a coluna 1, sobra um tabuleiro
. - Se colocamos dois dominos horizontais empilhados nas colunas 1 e 2, sobra um tabuleiro
. - Se colocamos um quadrado
nas colunas 1 e 2, também sobra um tabuleiro .
Passo 3
Da análise acima segue a recorrência
com condições iniciais:
Passo 4
Para resolver
que tem raízes
e
.
Logo, a solução geral é
Logo, a solução geral é
Usando
e
, obtemos
cuja solução é
. Portanto