Estoy leyendo el libro de Martin Aigner Curso de Enumeración y en $\S$ 3.3 La fórmula exponencial el autor enuncia y demuestra el siguiente teorema (en la página 117):
Teorema 3.8. Supongamos que $F(z) = zG(F(z))$ , $G(0) \neq 0$ . Entonces $$ [z^n] F(z) = \frac{1}{n} [z^{n-1}]G(z)^n. $$
Toma, $F$ y $G$ son series de potencias formales sobre $\Bbb{C}$ en la variable $z$ . Como corolario, el autor establece la Fórmula de inversión de Lagrange .
La demostración del teorema 3.8 comienza como sigue:
Prueba. Escribimos $F(z)$ y $G(z)$ en forma exponencial, $\widehat{F}(z) = \sum_{n \geq 1} f(n) \frac{z^n}{n!}$ , $\widehat{G}(z) = \sum_{n \geq 0} g(n) \frac{z^n}{n!}$ . Para un árbol rooteado $T$ en $\{1,\dotsc,n\}$ l $$ g^T := g(0)^{r_0} g(1)^{r_1} g(2)^{r_2} \dotsm, $$ donde $r_i$ es el número de vértices en $T$ con grado de salida $i$ (los bordes apuntan en dirección opuesta a la raíz). La secuencia $(r_0,r_1,r_2,\dotsc)$ se denomina tipo de $T$ . Desde $T$ tiene $n-1$ e $$ \sum_{i \geq 0} r_i = n, \quad \sum_{i \geq 0} ir_i = n-1. $$ Sea $f(n) = \sum_T g^T$ sobre todos los árboles enraizados en $\{1,\dotsc,n\}$ .
A continuación, se afirma lo siguiente
Reclamación 1. $\widehat{F}(z) = \sum_{n \geq 1} f(n) \frac{z^n}{n!}$ es la solución de la ecuación funcional $\widehat{F}(z) = z\widehat{G}(\widehat{F}(z))$ .
En la prueba de la afirmación, el autor muestra que si tomamos $\widehat{F}(z) = \sum_{n \geq 1} f(n) \frac{z^n}{n!}$ donde $f(n) = \sum_T g^T$ , entonces $\widehat{F}(z)$ satisface la ecuación funcional $\widehat{F}(z) = z\widehat{G}(\widehat{F}(z))$ . Sin embargo, no se hace ningún comentario sobre la singularidad.
¿Es obvio que esta elección particular de $\widehat{F}(z)$ es de hecho el solución a la ecuación funcional $\widehat{F}(z) = z\widehat{G}(\widehat{F}(z))$ ? ¿Cómo puedo ver esto?
El resto de la prueba es fácil de seguir. Tras establecer la afirmación 1, tenemos que $[z^n]F(z) = \frac{f(n)}{n!}$ por lo que sólo queda demostrar que $$ f(n) = (n-1)! [z^{n-1}]G(z)^n. $$ Para ello se afirma y demuestra lo siguiente.
Reclamación 2. Hay precisamente $\binom{n-1}{d_1 d_2 \dotso d_n}$ árboles enraizados en $\{1,\dotsc,n\}$ en cuyo vértice $i$ tiene grado de salida $d_i$ , $\sum_{i=1}^n d_i = n-1$ .
La demostración del Teorema 3.8 se completa fácilmente a partir de aquí.
