El camino a seguir para una prueba puramente calculadora a partir de la recurrencia es una función generadora exponencial.
$$f_1(n)=n^{n-2}$$
$$f_k(n)=\sum_{i=1}^{n-1}f_{k-1}(i)\cdot(n-i)^{n-i-2}\cdot{n-k \choose n-i-1}$$
Definir $T_k(z)=\sum_{n=k}^{\infty}\frac{f_k(n)}{(n-k)!}z^{n-k}$ . Tenga en cuenta que $T_1(z)=\sum_{n=1}^{\infty}\frac{n^{n-2}}{(n-1)!}z^{n-1}=\frac 1z \sum_{n=1}^{\infty}\frac{n^{n-1}}{n!}z^n=T(z)/z$ donde $T$ es la función de árbol con la propiedad $T(z)=z\exp(T(z))$ .
Tenemos $$\frac{f_k(n)}{(n-k)!}z^{n-k}=\sum_{i=1}^{n-1}\frac{f_{k-1}(i)}{(i-(k-1))!}z^{i-(k-1)}\cdot\frac{(n-i)^{n-i-2}}{(n-i-1)!}z^{n-i-1}$$
Suma esta relación para $n\ge k$ .
$$ T_k(z)=T_{k-1}(z) T_1(z) $$
Por lo tanto, $T_k(z)=T_1(z)^k=T(z)^k/z^k$ y $f_k(n)/(n-k)!$ es el coeficiente de $z^{n-k}$ en $T_k$ y, por tanto, el coeficiente de $z^n$ en $T^k$ .
Pero existe una versión de la fórmula de inversión de Lagrange que, partiendo de $T=z \exp T$ da una fórmula para el coeficiente de $z^n$ en $T^k$ .
Si $f(T(z))=z$ entonces este coeficiente es: $$\frac kn \langle z^{-k}\rangle f^{-n}(z) =\frac kn \langle z^{-k}\rangle z^n e^{nz} =\frac kn \langle z^{n-k}\rangle e^{nz} =\frac kn n^{n-k}/(n-k)! $$
Por lo tanto, $f_k(n)=n^{n-k-1}k$ .
