Generating functions for generating trees

Cyril Banderier; Philippe Flajolet; Danièle Gardy; Mireille Bousquet-Mélou; Alain Denise; Dominique Gouyou-Beauchamps

hal-00003258, version 1

Generating functions for generating trees

Cyril Banderier ( Author to contact preferably ) ^1, 2, Philippe Flajolet () ², Danièle Gardy ³, Mireille Bousquet-Mélou ⁴, Alain Denise ⁵, Dominique Gouyou-Beauchamps ⁵

Discrete Mathematics 246 (1-3) (2002) 29-55

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.

1: Laboratoire d'informatique de Paris-nord (LIPN)
CNRS : UMR7030 – Université Paris XIII - Paris Nord
2: ALGO (INRIA Rocquencourt)
INRIA
3: SMIS (INRIA Rocquencourt)
INRIA – CNRS : UMR8144 – Université de Versailles Saint-Quentin-en-Yvelines
4: Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
5: Laboratoire de Recherche en Informatique (LRI)
CNRS : UMR8623 – Université Paris XI - Paris Sud

hal-00003258, version 1
http://hal.archives-ouvertes.fr/hal-00003258
oai:hal.archives-ouvertes.fr:hal-00003258
From: Cyril Banderier <>
Submitted on: Wednesday, 10 November 2004 20:08:54
Updated on: Friday, 8 June 2007 18:03:23

See detailed view

Associated documents

PS :

PDF :

arXiv: math.CO/0411250

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="hal-00003258"><analytic>
<author><persName><forename>Cyril</forename><surname>Banderier</surname></persName>
<affiliation>
<orgName type="laboratory">LIPN</orgName>
<orgName type="team">Laboratoire d'informatique de Paris-nord</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7030</orgName>
<orgName type="institution">Université Paris XIII - Paris Nord</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">ALGO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Philippe</forename><surname>Flajolet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">ALGO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Danièle</forename><surname>Gardy</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">SMIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8144</orgName>
<orgName type="institution">Université de Versailles Saint-Quentin-en-Yvelines</orgName>
</affiliation>
</author>
<author><persName><forename>Mireille</forename><surname>Bousquet-Mélou</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Denise</surname></persName>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<author><persName><forename>Dominique</forename><surname>Gouyou-Beauchamps</surname></persName>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<title type="main" level="a">Generating functions for generating trees</title></analytic><monogr><title level="j" type="main">Discrete Mathematics</title><imprint><biblScope type="publicationDate">2002-00-00</biblScope><biblScope type="vol">246 (1-3)</biblScope><biblScope type="pp">29-55</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00003258</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00003258/PDF/eco.pdf</idno></biblStruct>
</listBibl>
</listBibl>