<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Generating functions for generating trees

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 01 Mar 2002Embargo end date: 01 Jan 2004 France Publisher:Elsevier BVJournal:Discrete Mathematics, volume 246, pages 29-55 (issn: 0012-365X,

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

doi: 10.1016/s0012-365x(01)00250-3 , 10.48550/arxiv.math/0411250

arXiv: http://arxiv.org/abs/math/0411250

Generating functions for generating trees

- Summary
- Subjects
- External Databases
  (1)
- Metrics

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.

This article corresponds, up to minor typo corrections, to the article submitted to Discrete Mathematics (Elsevier) in Nov. 1999, and published in its vol. 246(1-3), March 2002, pp. 29-55

Country

France

Related Organizations

View all View all

Keywords

FOS: Computer and information sciences, D-finite generating functions, Discrete Mathematics (cs.DM), permutations, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Exact enumeration problems, generating functions, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 510, Trees, Theoretical Computer Science, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science - Data Structures and Algorithms, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Generating trees, computational complexity, Walks on a half-line, 004, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Algebraic generating functions, generating trees, Combinatorics (math.CO), Computer Science - Discrete Mathematics

4xed

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	162
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%