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 2p-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: