Description trees and Tutte Formulas

Robert Cori 1 Gilles Schaeffer 2
2 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we introduce and enumerate families of \emph{description trees}. These families of trees consist of plane trees in which the nodes are labelled by non negative integers, and where the label of a each node satisfies a condition relating it to the labels of its sons. We give a recursive construction of these trees which translates simply in an equation for their generating function. By solving this equation via the quadratic method introduced by Brown and Tutte, we prove that this generating function is algebraic. For some families the number of trees we obtain is equal to the numbers given by W. T. Tutte to enumerate different kinds of planar maps. We provide bijections between description trees and corresponding families of planar maps to explain these equalities. Description trees are instances of objects that can be described by \emph{description operators}; we conjecture that such families of objects have algebraic generating functions. They were find also to be related to the enumeration of pattern avoiding permutations.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2003, 292 (1), pp.165-183
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:37:56
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17


  • HAL Id : inria-00099504, version 1


Robert Cori, Gilles Schaeffer. Description trees and Tutte Formulas. Theoretical Computer Science, Elsevier, 2003, 292 (1), pp.165-183. 〈inria-00099504〉



Consultations de la notice