Seja
o número de maneiras de se cobrir uma caixa
com retângulos
(você pode colocar cada dominó na horizontal ou vertical). Obtenha uma relação de recorrência para
.
Passo 1
Então, o que a gente tem aqui é um problema de contagem de maneiras de cobrir uma caixa com dimensões
usando retângulos de
. O objetivo é encontrar uma relação de recorrência para
, que representa o número de maneiras de fazer essa cobertura. Para resolver isso, vamos precisar entender um pouquinho sobre como esses retângulos podem ser posicionados na caixa e como isso afeta as possibilidades de cobertura conforme o tamanho
aumenta.
Passo 2
Primeiro, vamos pensar em como podemos colocar um retângulo de
na caixa
. Há duas opções principais: colocar o retângulo na horizontal ou na vertical.
- Horizontalmente: O retângulo ocupará toda a altura da caixa (já que a altura é 3) e se estenderá por 3 unidades na largura.
- Verticalmente: O retângulo ocupará 1 unidade na largura e 3 unidades na altura.
Passo 3
Vamos analisar cada caso para encontrar uma relação de recorrência.
-
Colocando o primeiro retângulo horizontalmente:
- Se colocarmos o primeiro retângulo horizontalmente, ele vai ocupar as primeiras 3 colunas da caixa
. - Depois de colocar esse retângulo, o que resta é uma caixa com dimensões
. - O número de maneiras de cobrir essa caixa restante é, justamente,
.
- Se colocarmos o primeiro retângulo horizontalmente, ele vai ocupar as primeiras 3 colunas da caixa
-
Colocando os primeiros três retângulos verticalmente:
- Alternativamente, podemos colocar três retângulos verticalmente, um em cada uma das primeiras três colunas da caixa.
- Isso ocupará as primeiras três colunas completamente.
- Após essa colocação, o que resta é uma caixa com dimensões
. - O número de maneiras de cobrir essa parte restante é
.
Passo 4
Com base nessas duas possibilidades, podemos somar as maneiras de cada caso para obter a relação de recorrência completa.
- Total de maneiras = Maneiras colocando o primeiro retângulo horizontalmente + Maneiras colocando os três primeiros retângulos verticalmente.
- Ou seja:
Resposta
A relação de recorrência para
é: