#####
Séminaire Lotharingien de Combinatoire, B09a (1983), 1
p.

[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 2^{p}-1.
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.

The following version are available: