Matrice de ramification des arbres binaires. (Ramification matrices of binary trees) (Q809098): Difference between revisions

The ramification matrices as a refinement of the Strahler number associated with each node of a binary tree were considered. The Strahler number also determines the number of registers for evaluating arithmetic expressions. The conjecture by X. G. Viennot that the ramification matrix of a binary tree takes asymptotically the form \[ \begin{matrix} \vdots \\ (1/2)\;(1/2)^ 2\;(1/2)^ 3\;...\;(1/2)^{n-1}\;(1/2)^ n \\ \vdots \end{matrix} \] at a number of tree nodes increasing to infinity was proved. The theorem was extended to the family of complete binary trees.