*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 n-1=5.

Passo 2

Definimos a_k como o número de árvores enraizadas não isomorfas com k vértices. Os valores iniciais conhecidos são
a_1 = 1,\quad a_2 = 1,\quad a_3 = 2,\quad a_4 = 4,\quad a_5 = 9.
Para n=6, cada árvore enraizada tem a raiz mais subárvores cujos tamanhos somam 5.

Passo 3

As partições de 5 em inteiros positivos determinam os tamanhos das subárvores ligadas à raiz:
5,\quad 4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.
Para cada partição, a contribuição ao total é o produto apropriado de a_k, ajustado pelo fato de subárvores de mesmo tamanho serem permutáveis (mas indistinguíveis).
Para cada caso:
  • Partição 5: contribuição =a_5 = 9.
  • Partição 4+1: contribuição =a_4\cdot a_1 = 4\cdot1 =4.
  • Partição 3+2: contribuição =a_3\cdot a_2 = 2\cdot1 =2.
  • Partição 3+1+1: contribuição =a_3\cdot\binom{a_1+2-1}{2} =2\cdot1 =2 (há uma única forma de escolher duas subárvores de tamanho 1).
  • Partição 2+2+1: contribuição =\binom{a_2+2-1}{2}\cdot a_1 =1\cdot1 =1.
  • Partição 2+1+1+1: contribuição =a_2\cdot\binom{a_1+3-1}{3} =1\cdot1 =1.
  • Partição 1+1+1+1+1: contribuição =\binom{a_1+5-1}{5} =1.

Passo 4

Somando todas as contribuições, obtemos
9 + 4 + 2 + 2 + 1 + 1 + 1 = 20.

Resposta

20

Exercícios de Livros Relacionados