A Strahler bijection between Dyck paths and planar trees

• Published in: Discrete mathematics 2002-03, Vol.246 (1), p.317-329
• Main Author: VIENNOT, Xavier Gérard
• Format: Article
• Language: English
• Subjects: Computer Science; Exact sciences and technology; Mathematics; Other; Sciences and techniques of general use
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/S0012-365X(01)00265-5

The Strahler number of binary trees has been introduced by hydrogeologists and rediscovered in computer science in relation with some optimization problems. Explicit expressions have been given for the Strahler distribution, i.e. binary trees enumerated by number of vertices and Strahler number. Two other Strahler distributions have been discovered with the logarithmic height of Dyck paths and the pruning number of forests of planar trees in relation with molecular biology. Each of these three classes are enumerated by the Catalan numbers, but only two bijections preserving the Strahler parameters have been explicited: by Françon between binary trees and Dyck paths, by Zeilberger between binary trees and forests of planar trees. We present here the missing bijection between forests of planar trees and Dyck paths sending the pruning number onto the logarithmic height. A new functional equation for the Strahler generating function is deduced. Some orthogonal polynomials appear, they are one parameter Tchebycheff polynomials. Le nombre de Strahler d'un arbre binaire a été introduit en hydrogéologie et redécouvert en informatique en relation avec certains problèmes d'optimisation. Des expressions explicites ont été données pour la distribution du paramètre nombre de Strahler, c'est-à-dire pour le nombre d'arbres binaires énumérés selon le nombre de sommets et leur nombre de Strahler. Depuis, deux autres distributions de Strahler ont été découvertes: la hauteur logarithmique des chemins de Dyck et l'ordre des forêts d'arbres planaires en relation avec la biologie moleculaire. Chacune de ces trois classes d'objets est énumérée par les nombres de Catalan, mais seulement deux bijections conservant les paramètres des distributions de Strahler ont été explicitées: l'une de Françon entre les arbres binaires et les mots de Dyck, l'autre de Zeilberger entre les arbres binaires et les forêts d'arbres planaires. Nous donnons une bijection entre les forêts d'arbres planaires et les mots de Dyck envoyant le paramètre ordre sur le paramètre hauteur logarithmique. Une nouvelle équation fonctionnelle est déduite pour la série génératrice associée la distribution de Strahler. Certains polynômes orthogonaux apparaissent, ce sont des extensions à un paramètre des polynômes de Tchebycheff.