Considere um reticulado . Vamos chamar de trajetória permitida um caminho poligonal que sai de , chega em , nunca toca pontos abaixo da diagonal e a cada passo sobe uma unidade ou anda para a direita uma unidade, veja a Figura 3.11. Seja o número de trajetórias permitidas. Determine uma relação de recorrência para .
Figura 3.11. Exemplo de trajetória permitida.
Passo 1
Então, vamos lá! A questão fala sobre um reticulado e pede para a gente encontrar uma relação de recorrência para o número de trajetórias permitidas, que são caminhos que vão de até , sempre subindo ou indo para a direita, sem tocar pontos abaixo da diagonal.
Para resolver isso, vamos usar conceitos de combinatória, especificamente as sequências de Catalan, que contam o número de caminhos que não cruzam a diagonal principal em um reticulado.
Passo 2
Primeiro, vamos entender o que é uma relação de recorrência. Basicamente, é uma maneira de expressar o termo em função dos termos anteriores, tipo , , e assim por diante. Isso ajuda a calcular passo a passo.
Passo 3
Agora, vamos pensar em como dividir nosso problema. Imagine que a última vez que o caminho toca a diagonal principal, ele divide o caminho em duas partes independentes. Ou seja, se dividirmos o caminho nesse ponto, a primeira parte vai de a esse ponto na diagonal, e a segunda parte vai desse ponto até .
Passo 4
Cada uma dessas partes é, na verdade, um caminho permitido menor. Se chamarmos o tamanho desse trecho menor de , então a primeira parte tem passos e a segunda parte tem passos (porque já contamos o ponto de divisão).
Passo 5
Como cada trecho pode ser qualquer uma das trajetórias permitidas que já calculamos antes, podemos multiplicar o número de trajetórias de cada parte. Ou seja, para cada , temos maneiras de fazer a primeira parte e maneiras de fazer a segunda parte.
Passo 6
Para encontrar todas as possibilidades, somamos essas multiplicações para todos os valores de de até . Isso nos dá a relação de recorrência: