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.

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|improve this question
add comment

1 Answer

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|improve this answer
    
thanks for help! –  John Lennon Feb 17 '13 at 22:52
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.