São dados n pontos em um círculo. Quantos n-ágonos (não necessariamente convexos) existem com vértices nesses pontos?

Passo 1

O enunciado diz que temos n pontos distintos sobre um círculo e quer saber de quantos n-ágonos podemos formar usando exatamente todos esses pontos como vértices, sem exigir que o polígono seja convexo. O que precisamos aqui é contar todas as formas de ligar esses n pontos de modo a formar um ciclo que passe por todos eles — isto é, contar todos os Hamiltonian cycles no grafo completo de n vértices — levando em conta as simetrias de rotação e reflexão.

Passo 2

Se associarmos cada vértice a um rótulo de 1 a n, toda maneira de “percorrer” esses n vértices numa volta corresponde a uma permutação dos n rótulos. Logo, inicialmente há
n!
maneiras de ordenar os vértices.

Passo 3

Porém, essa contagem com n! já conta cada n-ágono várias vezes, pois:
  1. Podemos começar a contagem em qualquer um dos n vértices sem alterar o ciclo.
  2. Podemos percorrer o ciclo em sentido horário ou anti-horário e obter o mesmo conjunto de arestas.
    Para ajustar essas duplicações, dividimos por n (as rotações) e por 2 (os dois sentidos), obtendo
n!2,n = (n-1)!2

Resposta

(n-1)!2

Exercícios de Livros Relacionados