Séminaire Lotharingien de Combinatoire, B09a (1983), 7
pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1984, 230/S-09, p.
167-173.]
Helmut Prodinger
Abzählprobleme bei Bäumen
Abstract.
This paper deals with the register function of binary trees.
This is just another name for the Horton-Strahler numbers of binary trees.
First, an extremely simple computation for the generating function of all
trees with register function =p is presented. Then, it is demonstrated,
how asymptotic formulae for the average value of the register function etc.
can be obtained by singularity analysis. [In 1990, Ph. Flajolet and
A.M. Odlyzko published an important survey in SIAM J. Disc. Math,
"Singularity Analysis of Generating Functions".] Then the register
function for Motzkin trees is discussed. Finally, there is the question
about a bijection between the binary trees with n nodes and register
function less than p and the binary trees with n nodes and leftsided height
less than 2p-1.
The following versions are available:
This is essentially a compilation of the two articles:
Helmut Prodinger, Die Bestimmung gewisser Parameter von binären
Bäumen mit Hilfe analytischer Methoden, Lecture Notes in Mathematics,
1114 (1985), 118-133.
Philippe Flajolet and Helmut Prodinger, Register Allocation for
unary-binary Trees, SIAM Journal on Computing 15 (1986), 629-640.