Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  Gadi A May 4 '11 at 18:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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