Dar una prueba combinatoria de la relación de recurrencia

Question

Que $F_n$ ser que la serie de bosques en la cima la $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Dar una prueba combinatoria de la recurrencia relación %#% $ #%

! Un árbol es un grafo conectado sin ciclos y un bosque es una Unión de separados de los árboles.

Por favor, ayuda!

Answer 1

Considere el árbol que contiene el vértice $n$. El % de índice $i$es el número de vértices de este árbol. Hay $i^{i-2}$ etiquetado bosques $i$ arreglos de los restantes vértices de $F_{n-i}$ $n-i$ vértices como un bosque, y usted puede elegir el $i-1$ vértices distintos de $n-1$ para formar el árbol que contiene $n$ $n$.