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.