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:
Resposta
A relação de recorrência para
é: