Descendants in heap ordered trees
or
a triumph of computer algebra

Abstract. A heap ordered tree with $n$ nodes (``size $n$'') is a planted plane tree together with a bijection from the nodes to the set $\{1,\dots,n\}$ which is monotonically increasing when going from the root to the leaves. We consider the number of descendants of the node $j$ in a (random) heap ordered tree of size $n\ge j$. Precise expressions are derived for the probability distribution and all (factorial) moments.
Related papers:
Pathlength, etc.
Depth of nodes


helmut@gauss.cam.wits.ac.za,

This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)