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
é:
Exercícios relacionados
Suponha a situação que se refere a eliminação de alguma substância no sangue. Em diversos casos, a quantidade
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:
Em que
é a constante de proporção.
Sendo assim, apresente a modelagem da função e sua representação gráfica.
Sendo assim, apresente a modelagem da função
Suponha que em um determinado tanque com água, no tempo
, encontra-se uma quantidade
de certa substância dissolvida em 100 galões. Suponha, ainda, que estão entrando no tanque
galões por minuto com
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
a quantidade dessa substância no tanque, a taxa de variação com relação ao tempo.
Seja
o número de permutações de
. Sem usar que
, deduza a equação de recorrência
(a) Como visto na Proposição 3.1.7, os Números de Stirling de segunda ordem
são definidos como o número de maneiras de distribuir
bolas numeradas em
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
Dica: considere
bolas numeradas em
urnas indistinguíveis. Há dois casos, ou a bola
está sozinha em uma urna, ou não está.
(b) Uma permutação dos números pode ser representada por uma composição de ciclos. Por exemplo, para
, a notação (142)(3)(576) representa a permutação
tal que
e
, o que completa o primeiro ciclo. Depois, temos que
, que é um ciclo de tamanho 1. Por fim,
e
. Os Números de Stirling de primeira ordem sem sinal, geralmente denotados por
, são definidos como o número de permutações de
elementos cuja decomposição em ciclos tem exatamente
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
(b) Uma permutação dos números
Dica: considere uma permutação de
elementos com
ciclos. Há dois casos, ou o
-é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 . 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 na sequência
definida por
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
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
onde
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
na sequência
definida por
onde
são os Números de Stirling de primeira ordem (com sinal).