A Strahler bijection between Dyck paths and planar trees

DOI10.1016/S0012-365X(01)00265-5MaRDI QIDQ1348155zbMATH OpenOpenAlexFDO

Authors Xavier Viennot

Publication date 15 May 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00265-5

zbMATH Keywords

binary treesDyck pathsStrahler number

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05)

Review text

The paper investigates binary trees \(B= (L,r,R)\), where \(L\) and \(R\) are the left and right subtree, respectively, and \(r\) denotes the root of \(B\). The Strahler number \(\text{St}(B)\) is defined by the following inductive process: Label the leaves by 1 and each internal vertex by \(\text{St}(R)+ 1\) if \(\text{St}(R)= \text{St}(L)\) and by \(\max\{\text{St}(L),\text{St}(R)\}\) otherwise. Then \(\text{St}(B)\) is the Strahler number of the root. The paper discusses several properties of binary trees with a given Strahler number and gives combinatorial consequences of these facts.

Recommendations

• scientific article; zbMATH DE number 2127732
• A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number
• scientific article; zbMATH DE number 894188
• Enumeration problems of trees
• A note on the Horton-Strahler number for random trees

Cited in

(11)

• Faster deterministic communication in radio networks
• Reductions of binary trees and lattice paths induced by the register function
• Information gathering in ad-hoc radio networks with tree topology
• Faster communication in known topology radio networks
• A combinatorial bijection on di-sk trees
• Fringe analysis of plane trees related to cutting and pruning
• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• scientific article; zbMATH DE number 2127732 (Why is no real title available?)
• scientific article; zbMATH DE number 1919510 (Why is no real title available?)
• A bijection on Dyck paths and its cycle structure
• Bijections for a class of labeled plane trees

This page was built for publication: A Strahler bijection between Dyck paths and planar trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1348155)