*2. Quantas árvores enraizadas não isomorfas existem com seis vértices?
Passo 1
O enunciado pede o número de árvores enraizadas não isomorfas com seis vértices. Esse é um problema de enumeração de árvores enraizadas não rotuladas: contamos as formas distintas de conectar seis vértices, escolhendo um deles como raiz, sem distinguir rótulos. Para resolver, vamos usar a ideia de que toda árvore enraizada se decompõe em subárvores penduradas na raiz, cujos tamanhos formam uma partição de
.
Passo 2
Definimos
como o número de árvores enraizadas não isomorfas com
vértices. Os valores iniciais conhecidos são
Para
, cada árvore enraizada tem a raiz mais subárvores cujos tamanhos somam
.
Passo 3
As partições de
em inteiros positivos determinam os tamanhos das subárvores ligadas à raiz:
Para cada partição, a contribuição ao total é o produto apropriado de
, ajustado pelo fato de subárvores de mesmo tamanho serem permutáveis (mas indistinguíveis).
Para cada caso:
- Partição
: contribuição . - Partição
: contribuição . - Partição
: contribuição . - Partição
: contribuição (há uma única forma de escolher duas subárvores de tamanho 1). - Partição
: contribuição . - Partição
: contribuição . - Partição
: contribuição .
Passo 4
Somando todas as contribuições, obtemos