Abstract :
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.
Résumé
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.
