Description trees and Tutte formulas

In this paper we introduce and enumerate families of description trees. These families of trees consist of plane trees in which the nodes are labelled by nonnegative integers, and where the label of each node satisfies a condition relating it to the labels of its sons. We give a recursive construction of these trees which translates simply in an equation for their generating function. By solving this equation via the quadratic method introduced by Brown and Tutte, we prove that this generating function is algebraic. For some families the number of trees we obtain is equal to the numbers given by Tutte to enumerate different kinds of planar maps. We provide bijections between description trees and corresponding families of planar maps to explain these equalities. Description trees are instances of objects that can be described by description operators; we conjecture that such families of objects have algebraic generating functions. They were find also to be related to the enumeration of pattern avoiding permutations.