Seja a_n o número de maneiras de se cobrir uma caixa 1 * n com retângulos 1 x 1,1 x 2 e 1 x 3. Obtenha uma relação de recorrência para a_n.

Passo 1

Beleza, vamos lá! A gente tem uma caixa que é de tamanho 1 * n e queremos cobri-la usando retângulos que são , e 1 x 3. A questão está pedindo para a gente encontrar uma relação de recorrência para a_n, 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 a_n em função de , e .

Passo 3

Agora, imagina que estamos começando a cobrir a caixa de 1 * n. A primeira peça que colocamos na caixa pode ser de três tamanhos diferentes:
  1. 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 é .
  2. 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 .
  3. Retângulo 1 x 3: 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 1 * n é 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 1 * n, 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 a_n é:

Exercícios relacionados

Suponha a situação que se refere a eliminação de alguma substância no sangue. Em diversos casos, a quantidade S(t) dessa certa substância na corrente sanguínea, registrada sob a relação ao excesso do que é natural encontrar, diminuirá a uma taxa duplamente proporcional a esse mesmo excesso no instante em que é registrado. A situação pode ser modelada da seguinte forma:
dS(t)/dt = -2 * k * S
Em que k > 0 é a constante de proporção.
Sendo assim, apresente a modelagem da função S(t) e sua representação gráfica.
Suponha que em um determinado tanque com água, no tempo t = 0, encontra-se uma quantidade S0 de certa substância dissolvida em 100 galões. Suponha, ainda, que estão entrando no tanque g galões por minuto com 0,2 l b dessa substância por galão e que a taxa de escoamento é a mesma da entrada. Encontre a lei diferencial que governa esse acontecimento, sob a hipótese de que a substância não irá se degenerar por algum motivo dentro do tanque, sendo que a única forma de entrada e saída pelo fluxo que estamos considerando, e denotando por S(t) a quantidade dessa substância no tanque, a taxa de variação com relação ao tempo.
Seja Pn o número de permutações de {1, ..., n}. Sem usar que Pn = n!, deduza a equação de recorrência
P_n = n * P_{n-1}, ∀ n ≥ 2; P_{1} = 1
(a) Como visto na Proposição 3.1.7, os Números de Stirling de segunda ordem S(n, k) são definidos como o número de maneiras de distribuir n bolas numeradas em k urnas indistinguíveis, sem que nenhuma urna fique vazia. Sem utilizar a fórmula obtida na Proposição 3.1.7 ou seja, apresentando um argumento combinatório, mostre que os Números de Stirling de segunda ordem satisfazem a recorrência
S(n, k)=k cdot S(n-1, k)+S(n-1, k-1)
Dica: considere n bolas numeradas em k urnas indistinguíveis. Há dois casos, ou a bola n está sozinha em uma urna, ou não está.
(b) Uma permutação dos números 1, ldots, n pode ser representada por uma composição de ciclos. Por exemplo, para n=7, a notação (142)(3)(576) representa a permutação f:1, ldots, 7 1, ldots, 7 tal que f(1)=4, f(4)=2 e f(2)=1, o que completa o primeiro ciclo. Depois, temos que f(3)=3, que é um ciclo de tamanho 1. Por fim, f(5)=7, f(7)=6 e f(6)=5. Os Números de Stirling de primeira ordem sem sinal, geralmente denotados por [ln k], são definidos como o número de permutações de n elementos cuja decomposição em ciclos tem exatamente k ciclos. Por exemplo, a permutação (142)(3)(576) anterior tem três ciclos. Mostre que os Números de Stirling de primeira ordem sem sinal satisfazem à recorrência
[l n k ]=(n-1) cdot[c n-1 k ]+[l n-1 k-1 ]
Dica: considere uma permutação de n elementos com k ciclos. Há dois casos, ou o n-ésimo elemento está num ciclo de tamanho um, ou não.
Observação. A título de curiosidade, comentamos aqui que os Números de Stirling de primeira ordem com sinal (ou simplesmente Números de Stirling de primeira ordem) são definidos por s(n, k)=(-1)^n-k[ln k]. E os nomes de primeira
ordem e de segunda ordem se devem a uma conexão entre estes dois tipos de números, a chamada transformada de Stirling. A transformada de Stirling é a operação que leva uma sequência an na sequência bn definida por
bn=sumk=1^n S(n, k) ak
onde S(n, k) são os Números de Stirling de segunda ordem. Curiosamente, a inversa da transformada de Stirling é a operação que leva uma sequência an na sequência bn definida por
bn=sumk=1^n s(n, k) ak
onde s(n, k) são os Números de Stirling de primeira ordem (com sinal).