Generating functions for generating trees (Q1348138)

This paper deals with generating trees which have been used, in the past, to enumerate permutations with forbidden subsequences, and have provided a useful description of numerous classical combinatorial structures. Each node of a generating tree corresponds to an object, and the branch to the code provides the choices made in constructing the object. It is shown that generating trees lead to a fast computation of enumerating sequences of relatively low computational complexity and provide fast random generation algorithms. The authors study here the links between the structural properties of the rewriting rules defining such trees and the corresponding generating function---be it rational, algebraic, or transcendental. A discussion of the holonomy of transcendental systems is also included, and there are numerous illustrative examples from different aspects of combinatorics.