Explique como Cayley usou árvores para enumerar o número de certos tipos de hidrocarbonetos.
Passo 1
O problema de Cayley consistia em contar quantos isômeros (hidrocarbonetos químicos distintos) existem de um dado tipo de composto acíclico saturado, por exemplo os alcanos \– hidrocarbonetos
. O conteúdo aqui é teoria de grafos e geração de funções: vamos representar cada esqueleto de carbono como uma árvore e depois usar métodos de contagem de árvores para obter o número de estruturas químicas possíveis.
Passo 2
Modelagem por árvores
Cada átomo de carbono vira um vértice e cada ligação C–C vira uma aresta. Como a molécula é acíclica e conectada, o grafo é exatamente uma árvore. Os átomos de hidrogênio não entram no grafo, pois eles “preenchem” apenas as valências livres do carbono, e não afetam a forma de ramificação.
Cada átomo de carbono vira um vértice e cada ligação C–C vira uma aresta. Como a molécula é acíclica e conectada, o grafo é exatamente uma árvore. Os átomos de hidrogênio não entram no grafo, pois eles “preenchem” apenas as valências livres do carbono, e não afetam a forma de ramificação.
Passo 3
Restrição de valência
Químicamente cada carbono tem valência 4, ou seja, cada vértice da árvore pode ter grau até 4. Na prática, quando “enraizamos” a árvore num carbono especial, esse nó-raiz tem até 4 “ramificações” e cada descendente pode ter até 3 ramificações (uma veio de cima e até três abaixo).
Químicamente cada carbono tem valência 4, ou seja, cada vértice da árvore pode ter grau até 4. Na prática, quando “enraizamos” a árvore num carbono especial, esse nó-raiz tem até 4 “ramificações” e cada descendente pode ter até 3 ramificações (uma veio de cima e até três abaixo).
Passo 4
Função geradora para árvores enraizadas
Cayley considerou primeiro árvores enraizadas (com um carbono marcado como raiz) em que cada vértice descende em até 3 subárvores. Se chamarmos de a função geradora exponencial em que o coeficiente de
é o número de árvores enraizadas com
carbonos, obtemos o equilíbrio combinatório
Cayley considerou primeiro árvores enraizadas (com um carbono marcado como raiz) em que cada vértice descende em até 3 subárvores. Se chamarmos de
Aqui o fator
conta a própria raiz, e
distribui até três subárvores por ela (cada subárvore pode ser vazia, que corresponde a um ramo que termina num carbono saturado apenas por hidrogênio).
Passo 5
Passagem de árvores enraizadas a não enraizadas
Para voltar às árvores não enraizadas (isto é, esquemas de alcanos sem marcar um átomo como “raiz”), Cayley usou uma fórmula que relaciona os coeficientes de com o número
de árvores não enraizadas de
vértices. Em essência, cada árvore não enraizada de
vértices gera
árvores enraizadas por escolha da raiz, salvo fatores de simetria que são tratados por correções finitas. O resultado é que
Para voltar às árvores não enraizadas (isto é, esquemas de alcanos sem marcar um átomo como “raiz”), Cayley usou uma fórmula que relaciona os coeficientes de
e Cayley calculou explicitamente os primeiros termos dessa sequência para obter o número de isômeros de
para
de 1 até, digamos, 10 ou 12.
Passo 6
Conclusão e valores obtidos
Usando esse método de geração e extração de coeficientes (via inversão de Lagrange, ainda que não com esse nome, e contagem de simetrias), Cayley produziu a lista clássica de quantidade de alcanos:
Usando esse método de geração e extração de coeficientes (via inversão de Lagrange, ainda que não com esse nome, e contagem de simetrias), Cayley produziu a lista clássica de quantidade de alcanos:
para
. Esses números coincidem com o número de hidrocarbonetos distintos de fórmula
.
Resposta
Cayley mapeou esqueletos de alcanos em árvores com grau máximo 4, construiu a função geradora
para árvores enraizadas, usou inversão de Lagrange para obter os coeficientes e depois dividiu por
(com correções de simetria) para contar as árvores não enraizadas, que correspondem exatamente aos isômeros de
.