4
$\begingroup$

I have a sequence of functions $f_k(n)$ defined as follows:

$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}$

My goal is to find and prove a closed-form formula for this sequence (i.e. a formula for $f_k(n)$ which does not depend on $f_{k-1}$).

Actually, I already know (from another source) that the solution is $f_k(n)=n^{n-k-1}k$. However, I still want to know if there is a good method for finding the solution from the equation itself, and most importantly, I want to prove that the closed-form formula is correct.

$\endgroup$
3
$\begingroup$

The way to go for a purely calculatory proof from the recurrence is exponential generating functions.

$$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}$$

Define $T_k(z)=\sum_{n=k}^{\infty}\frac{f_k(n)}{(n-k)!}z^{n-k}$. Note that $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$ where $T$ is the tree function with property $T(z)=z\exp(T(z))$.

We have $$\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}$$

Sum this relation for $n\ge k$.

$$ T_k(z)=T_{k-1}(z) T_1(z) $$

Therefore, $T_k(z)=T_1(z)^k=T(z)^k/z^k$ and $f_k(n)/(n-k)!$ is the coefficient of $z^{n-k}$ in $T_k$ and thus the coefficient of $z^n$ in $T^k$.

But there is a version of the Lagrange inversion formula that, starting from $T=z \exp T$ gives a formula for the coefficient of $z^n$ in $T^k$.

If $f(T(z))=z$ then this coefficient is: $$\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)! $$

Therefore, $f_k(n)=n^{n-k-1}k$.

$\endgroup$
  • $\begingroup$ The formula counts sequences of $k$ labeled trees with a total number of $n$ vertices; however, my main interest is in the recurrence relation and whether there is some straightforward way of using it to obtain the result. $\endgroup$ – Gadi A May 4 '11 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.