×

zbMATH — the first resource for mathematics

Generating functions for generating trees. (English) Zbl 0997.05007
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.

MSC:
05A15 Exact enumeration problems, generating functions
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI arXiv