Considere um reticulado n * n. Vamos chamar de trajetória permitida um caminho poligonal que sai de (0,0), chega em (n, n), 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 a_n o número de trajetórias permitidas. Determine uma relação de recorrência para a_n.
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 é:

Exercícios relacionados