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.
para
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, é: