Geodesic
Abzählprobleme bei Bäumen
Séminaire lotharingien de combinatoire, Tome 09 (1983)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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},
     publisher = {mathdoc},
     volume = {09},
     year = {1983},
     url = {http://geodesic.mathdoc.fr/item/SLC_1983_09_a0/}
}
TY  - JOUR
AU  - Helmut Prodinger
TI  - Abzählprobleme bei Bäumen
JO  - Séminaire lotharingien de combinatoire
PY  - 1983
VL  - 09
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1983_09_a0/
ID  - SLC_1983_09_a0
ER  - 
%0 Journal Article
%A Helmut Prodinger
%T Abzählprobleme bei Bäumen
%J Séminaire lotharingien de combinatoire
%D 1983
%V 09
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1983_09_a0/
%F 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/