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 é:

Exercícios relacionados

Uma triangulação de um polígono convexo é uma divisão de em triângulos usando algumas de suas diagonais de modo que suas diagonais não se intersectem, veja a Figura 3.10. Encontre uma relação de recorrência
Figura 3.10. Duas triangulações diferentes do pentágono .
para , onde denota o número de triangulações de um polígono convexo de lados.
Dica: para ajudar na contagem, fixe um lado do polígono e o triângulo que contém esse lado, e faça a contagem. Depois some sobre todos os triângulos possíveis que contém esse lado.
Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência
Calcule , sendo dada por:
Os limites a seguir apresentam indeterminações do tipo . Esses limites apresentam razões entre polinômios, calcule-os: