São dados
pontos em um círculo. Quantos
-ágonos (não necessariamente convexos) existem com vértices nesses pontos?
Passo 1
O enunciado diz que temos
pontos distintos sobre um círculo e quer saber de quantos
-á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
pontos de modo a formar um ciclo que passe por todos eles — isto é, contar todos os Hamiltonian cycles no grafo completo de
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
a
, toda maneira de “percorrer” esses
vértices numa volta corresponde a uma permutação dos
rótulos. Logo, inicialmente há
maneiras de ordenar os vértices.
Passo 3
Porém, essa contagem com
já conta cada
-ágono várias vezes, pois:
- Podemos começar a contagem em qualquer um dos
vértices sem alterar o ciclo. - 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(as rotações) e por (os dois sentidos), obtendo