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.

Passo 1

Beleza, vamos lá! O enunciado fala sobre triangulação de um polígono convexo. Isso significa dividir um polígono com lados em triângulos usando suas diagonais de forma que elas não se cruzem. Nosso objetivo aqui é encontrar uma relação de recorrência para , que representa o número de maneiras diferentes de fazer essa triangulação para um polígono convexo de lados. Para resolver isso, vamos fixar um lado do polígono e analisar as possíveis triangulações que envolvem esse lado.

Passo 2

Primeiro, vamos fixar um lado do polígono convexo, digamos o lado . Ao fixar esse lado, any triangulação deve incluir um triângulo que tem como um dos seus lados. Vamos chamar esse triângulo de , onde é um vértice não adjacente a .

Passo 3

Agora, ao formar o triângulo , dividimos o polígono original em duas partes menores:
  1. Uma parte à esquerda do triângulo , que é um polígono convexo com lados.
  2. Uma parte à direita do triângulo , que é um polígono convexo com lados.

Passo 4

Cada uma dessas partes menores também pode ser triangulada de várias maneiras. Se representa o número de triangulações para um polígono de lados, então:
  • A parte à esquerda pode ser triangulada de maneiras.
  • A parte à direita pode ser triangulada de maneiras.

Passo 5

Como as triangulações das duas partes são independentes, o número total de triangulações que incluem o triângulo é o produto de e .

Passo 6

Para encontrar a relação de recorrência total, precisamos somar essas possibilidades para todos os valores possíveis de . Ou seja, devemos considerar todos os vértices onde o triângulo pode ser formado fixando o lado .

Passo 7

Isso nos leva à relação de recorrência:
Onde:
  • é o número de triangulações para um polígono de lados.
  • A soma vai de até , cobrindo todos os vértices possíveis para formar o triângulo fixo.

Resposta

A relação de recorrência para , o número de triangulações de um polígono convexo de lados, é:

Exercícios relacionados

Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência
Encontre uma recorrência para , o número de sequências de letras dentre ou , que não têm letras vizinhas.
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.
Calcule , sendo dada por: