Quantas centopéias não isomorfas com seis vértices existem?
Passo 1
O enunciado pede o número de centopéias não isomorfas com seis vértices. Aqui o conteúdo é Teoria de Grafos (árvores especiais). Uma centopéia é uma árvore obtida a partir de um caminho simples (chamado de espinha) a que se pode anexar no máximo uma folha a cada vértice da espinha.
Passo 2
Seja
o número de vértices da espinha e
o número de folhas anexadas. Temos
pois cada vértice da espinha admite no máximo uma folha. Da segunda desigualdade resulta
Logo só podem ocorrer
.
Passo 3
Para cada
calculamos
e contamos as maneiras de escolher
vértices de uma espinha com
vértices, até isomorfismo. A única simetria da espinha é a reflexão (reversão da ordem dos vértices).
Passo 4
Número de não-isomorfismos:
casos distintos (âncora em extremidade, penúltimo, ou central).
Passo 5
Passo 6
Número de não-isomorfismos:
Passo 7
Somando todos os casos: