Generating functions for generating trees

• Published in 2002
• Added on 2020-10-24

Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the construction of the object. Generating trees lead to a fast computation of enumeration sequences (sometimes, to explicit formulae as well) and provide efficient random generation algorithms. We investigate the links between the structural properties of the rewriting rules defining such trees and the rationality, algebraicity, or transcendence of the corresponding generating function.

Links

• https://www.sciencedirect.com/science/article/abs/pii/S0012365X01002503

Other information

BibTeX entry

@article{Generatingfunctionsforgeneratingtrees,
	key = {Generatingfunctionsforgeneratingtrees},
	type = {article},
	title = {Generating functions for generating trees},
	author = {Cyril Banderier and Mireille Bousquet-M{\'{e}}lou and Alain Denise and Philippe Flajolet and Danièle Gardy and Dominique Gouyou-Beauchamps},
	abstract = {Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the construction of the object. Generating trees lead to a fast computation of enumeration sequences (sometimes, to explicit formulae as well) and provide efficient random generation algorithms. We investigate the links between the structural properties of the rewriting rules defining such trees and the rationality, algebraicity, or transcendence of the corresponding generating function.},
	comment = {},
	date_added = {2020-10-24},
	date_published = {2002-04-10},
	urls = {https://www.sciencedirect.com/science/article/abs/pii/S0012365X01002503},
	collections = {integerology},
	url = {https://www.sciencedirect.com/science/article/abs/pii/S0012365X01002503},
	year = 2002,
	urldate = {2020-10-24}
}