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:
Uma parte à esquerda do triângulo , que é um polígono convexo com lados.
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, é: