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

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} \binom{n-1}{i-1} i^{i-2} F_{n-i} $$

! A tree is a connected graph without cycles and a forest is a disjoint union of trees.

Please, help!

share|cite|improve this question

Consider the tree containing the vertex $n$. The index $i$ is the number of vertices in this tree. There are $i^{i-2}$ labeled forests with $i$ vertices and $F_{n-i}$ arrangements of the remaining $n-i$ vertices as a forest, and you can choose $i-1$ of the $n-1$ vertices other than $n$ to form the tree containing $n$.

share|cite|improve this answer
thanks for help! – John Lennon Feb 17 '13 at 22:52

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.