THE MOMENTS OF THE SACKIN INDEX OF RANDOM $\boldsymbol{d}$-ARY INCREASING TREES

Abstract

For any fixed integer $d\geq 2$, the $d$-ary increasing tree is a rooted, ordered, labeled tree where the out-degree is bounded by $d$, and the labels along each path beginning at the root increase. Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances and the Sackin index is defined as the sum of the depths of its leaves. We study these quantities in random $d$-ary increasing trees.