Uma escada possui
degraus,
, determine o número de maneiras distintas que se pode subir a escada se valem, simultaneamente, as seguintes restrições
em nenhum passo é permitido descer qualquer quantidade de degraus.
em nenhum passo é permitido descer qualquer quantidade de degraus.
Passo 1
O enunciado dá uma escada com
degraus, com
, e pede: determinar o número de maneiras distintas de subir a escada sabendo que, em nenhum passo, é permitido descer qualquer quantidade de degraus.
Informações relevantes dadas:
Informações relevantes dadas:
- A escada tem
degraus. - Em cada movimento só é permitido subir (não descer) uma quantidade positiva de degraus.
- A ordem dos movimentos importa (por exemplo, subir
depois é diferente de subir depois ).
O que se quer: o número total de sequências possíveis de movimentos (cada movimento é um inteiro positivo de degraus) cuja soma é exatamente.
Passo 2
Interpretação precisa do problema (o que significa “maneira de subir”):
Uma “maneira” é uma sequência finita com
tal que cada
é um inteiro positivo (
) e
Uma “maneira” é uma sequência finita
Essas sequências são chamadas de composições do inteiro
. Vou explicar o que é uma composição e por que contar composições responde ao problema.
Passo 3
Definição e exemplo concreto de composição:
Uma composição de é uma maneira de escrever
como soma ordenada de inteiros positivos. A ordem importa. Exemplos para ficar confortável:
Uma composição de
- Para
: as composições são . Total: . - Para
: composições: , . Total: . - Para
: composições: , , , . Total: . - Para
: composições: , , , , , , , . Total: .
Repare no padrão numéricoque sugere potência de .
Passo 4
Prova combinatória direta (argumento dos espaços entre degraus):
Pense em símbolos “1” alinhados:
(há
desses). Entre esses
uns há exatamente
lacunas (ou “gaps”) onde podemos, opcionalmente, colocar uma quebra para separar blocos. Cada forma de agrupar os
s em blocos contíguos determina uma composição: por exemplo, para
, se não colocarmos quebras em dois primeiros gaps, colocarmos quebra no terceiro e não no quarto, obtemos o agrupamento
. Para cada um dos
gaps há duas opções independentes: colocar quebra ou não colocar quebra. Logo o número total de escolhas de quebra é
Pense em
Cada escolha de subconjunto de gaps corresponde a exatamente uma composição (agrupamento) e cada composição é obtida por exatamente uma configuração de quebras — temos, portanto, uma bijeção. Assim o número de composições de
(isto é, o número de maneiras de subir a escada) é
.
Passo 5
Prova alternativa por recorrência e indução (útil para a prova escrita na prova):
Defina como o número procurado. Se o primeiro movimento sobe
degraus com
, o restante precisa cobrir
degraus, e há
maneiras para isso. Portanto
Defina
Mudando a indexação com
obtemos
Tomando
em vez de
temos
Subtraindo as duas igualdades:
Com condição inicial
(só a sequência
), essa recorrência dá
por indução simples:
e se
então
.
Passo 6
Resumo final e observações:
- O problema é equivalente a contar composições de
(somatórios ordenados de inteiros positivos que somam ). - Pelo argumento dos gaps (ou pela recorrência), o número de maneiras é
para todo .
Isso bate com os exemplos numéricos:, , , , etc. Vai dar certo na prova — respira, tá dominado!