Función generadora del número de árboles no etiquetados en $n$ vértices

Question

Según Secuencia OEIS A000055 si $(T_n)$ denota la secuencia del número de árboles con $n$ vértices no etiquetados, entonces tiene la función generadora $$G(x)=1+A(x)-A^2(x)/2+A(x^2)/2=\sum_{n=0}^{\infty}T_n x^n,$$ donde $A(x)=x + x^2 + 2x^3 + 4x^4 + 9x^5 + 20x^6+\cdots$ es la función generadora de Secuencia OEIS A000081 .

He intentado deducir esta función generadora por mi cuenta, pero no tengo ninguna pista. ¿Puede alguien darme una explicación detallada de esta fórmula?
Gracias de antemano.

Answer 1

La conexión entre las funciones generadoras para árboles no etiquetados y para árboles enraizados no etiquetados se deriva en El número de árboles Richard Otter, Anales de Matemáticas , $2$ nd Vol. $49$ No. $3$ (Jul., $1948$ ), pp. $583$ - $599$ (en la sección "Árboles" a partir de la p. $587$ ).

La prueba se basa en el hecho de que si se forman clases de equivalencia de los vértices y aristas de un árbol en función de si se transforman unos en otros por isomorfismos del árbol, se pueden elegir representantes que formen un subárbol, con la excepción de lo que Otter llama una "arista de simetría", una arista que se invierte por un isomorfismo del árbol y forma una clase de equivalencia propia. Dado que el número de vértices del subárbol es uno más que el número de aristas, se deduce que el número $t_n$ de árboles sin etiquetar es el número $a_n$ de árboles enraizados no etiquetados menos el número $b_n$ de árboles no etiquetados "con arista" (es decir, árboles no etiquetados con una arista distinguida, que no debe ser una arista de simetría). El número de árboles enraizados en una arista puede contarse contando las formas de dividir árboles en una arista y rootear los dos árboles resultantes en los vértices de la arista:

$$ b_n=\frac12\left(\sum_{k=0}^na_ka_{n-k}-a_{n/2}\right)\;, $$

donde el factor $\frac12$ tiene en cuenta la doble contabilidad, $a_{n/2}=0$ si $n$ es impar, y el segundo término resta la contribución de los bordes de simetría. Teniendo en cuenta el caso especial $n=0$ donde tenemos el árbol vacío pero no el árbol vacío rooteado, tenemos

$$ t_n=\delta_{n0}+a_n-b_n\;, $$

y traduciendo esto a funciones generadoras se obtiene

$$ T(x)=1+A(x)-\frac12\left(A(x)^2-A(x^2)\right)\;. $$