Seja a_n o número de maneiras de se cobrir uma caixa 3 * n com retângulos 1 x 3 (você pode colocar cada dominó na horizontal ou vertical). Obtenha uma relação de recorrência para a_n.

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.
  1. 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, .
  2. 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 é:

Exercícios relacionados