Abzählprobleme bei Bäumen
Séminaire lotharingien de combinatoire, Tome 09 (1983)
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.
@article{SLC_1983_09_a0,
author = {Helmut Prodinger},
title = {Abz\"ahlprobleme bei {B\"aumen}},
journal = {S\'eminaire lotharingien de combinatoire},
year = {1983},
volume = {09},
url = {http://geodesic.mathdoc.fr/item/SLC_1983_09_a0/}
}
Helmut Prodinger. Abzählprobleme bei Bäumen. Séminaire lotharingien de combinatoire, Tome 09 (1983). http://geodesic.mathdoc.fr/item/SLC_1983_09_a0/