Uma triangulação de um polígono convexo Pn é uma divisão de Pn 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 A B C D E.
para a_n, onde a_n denota o número de triangulações de um polígono convexo de n 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