Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


$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|cite|improve this question
up vote 3 down vote accepted

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


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

Your Answer


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.