A recursive algorithm for trees and forests

Trees or rooted trees have been generously studied in the literature. A forest is a set of trees or rooted trees. Here we give recurrence relations between the number of some kind of rooted forest with k roots and that with k+1 roots on {1,2,…,n}. Classical formulas for counting various trees such as rooted trees, bipartite trees, tripartite trees, plane trees, k-ary plane trees, k-edge colored trees follow immediately from our recursive relations.