Seja
o número de maneiras de se cobrir uma caixa
com retângulos
e
. Obtenha uma relação de recorrência para
.
Passo 1
Beleza, vamos lá! A gente tem uma caixa que é de tamanho
e queremos cobri-la usando retângulos que são
,
e
. A questão está pedindo para a gente encontrar uma relação de recorrência para
, que é o número de maneiras de fazer essa cobertura. Vamos precisar usar conceitos de recorrência e combinatória para resolver isso.
Passo 2
Primeiro, vamos entender o que é uma relação de recorrência. É tipo uma fórmula que relaciona o termo atual de uma sequência com os anteriores. No nosso caso, queremos expressar
em função de
,
e
.
Passo 3
Agora, imagina que estamos começando a cobrir a caixa de
. A primeira peça que colocamos na caixa pode ser de três tamanhos diferentes:
-
Retângulo
: Se colocarmos esse primeiro retângulo, ele ocupa uma posição, e sobra uma caixa de . O número de maneiras de cobrir essa parte restante é . -
Retângulo
: Se usarmos esse retângulo primeiro, ele ocupa duas posições, deixando uma caixa de . As maneiras de cobrir essa parte são . -
Retângulo
: Colocando esse primeiro, ele ocupa três posições, sobrando uma caixa de . As maneiras de cobrir essa parte são .
Passo 4
Como qualquer uma dessas três opções pode ser a primeira peça que colocamos, o total de maneiras de cobrir a caixa de
é a soma das maneiras de cada caso. Então, a relação de recorrência fica:
Passo 5
Essa fórmula nos diz que, para encontrar o número de maneiras de cobrir uma caixa de
, a gente soma as maneiras de cobrir as caixas de tamanhos menores:
,
e
. É uma forma eficiente de resolver o problema usando passos menores.
Resposta
A relação de recorrência para
é: