On Generating Functions of Generating Trees

Abstract : Generating trees describe conveniently certain families of combinatorial objects: 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) while providing efficient random generation algorithms. In this paper, we investigate the relationship between structural properties of the rules defining such trees and the rationality, algebraicity, or transcendence of the corresponding generating functions.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073011
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:35:06 AM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, March 24, 2011 - 12:25:23 PM

Identifiers

  • HAL Id : inria-00073011, version 1

Collections

Citation

Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, et al.. On Generating Functions of Generating Trees. [Research Report] RR-3661, INRIA. 1999. ⟨inria-00073011⟩

Share

Metrics

Record views

142

Files downloads

167