Enumeração de Estruturas

Enumerar uma estrutura é contar, para cada n, quantos objetos combinatórios de um tipo existem. O tipo determina o que entra na conta: se a ordem importa, se os vértices têm rótulo, se o ciclo é permitido, qual o incremento da camada.

A função p(n), o teto de floresta, Cayley, Kirchhoff e as recorrências deste tópico — e as árvores geradoras na teoria dos grafos — reutilizam essa mesma conta.

As páginas se agrupam em quatro blocos. O primeiro decompõe n em somandos positivos sem ordem, ou um conjunto em blocos disjuntos.

O segundo conta grafos simples rotulados e lê o máximo de arestas que uma floresta admite.

O terceiro conta árvores rotuladas em n vértices e árvores geradoras de um grafo G dado.

O quarto define aₙ pelos termos anteriores: último bloco de uma composição, ou a camada nova de um polígono.

Grafos calcula o teto |E| ≤ n−1 quando a questão pede o máximo de arestas sem ciclo. Árvores conta quantas árvores rotuladas existem: nⁿ⁻², pelo código de Prüfer.

τ(Kₙ) = nⁿ⁻² está em Árvores. Redes monta a laplaciana L e calcula τ(G) por um cofator, quando faltam arestas.

p(n) está em Partições: somandos positivos em ordem não crescente. Composições com partes 1 e 2, em que (2,1) e (1,2) são distintas, estão em Relações de Recorrência.

A classificação linear, homogênea e de ordem, e o incremento constante aₙ = aₙ₋₁ + c, estão em Relações de Recorrência. Substituir k em Δₖ(n) = (k−2)n − (k−3) e iterar Fₖ(n) está em Números poligonais.