Reachability results in labelled t-ary trees

Abstract

In this paper, we prove some new formulas in the enumeration of labelled t-ary trees by path lengths. We treat trees having their edges oriented from a vertex of lower label towards a vertex of higher label. Among other results, we obtain counting formulas for the number of t-ary trees on n vertices in which there are paths of length ` starting at a root with label i and ending at a vertex, sink, leaf sink, first child, non-first child and non-leaf. For each statistic, the average number of these reachable vertices is obtained for any random t-ary tree.