A note on naturally embedded ternary trees (Q553995)

Summary: In this note we consider ternary trees naturally embedded in the plane in a deterministic way. The root has position zero, or in other words label zero, and the three children of a node with position \(j \in \mathbb Z\) have positions \(j - 1,\, j\), and \(j + 1\). We derive the generating function of embedded ternary trees where all internal nodes have labels less than or equal to \(j\), with \(j \in \mathbb N\). Furthermore, we study the generating function of the number of ternary trees of size \(n\) with a given number of internal nodes with label \(j\). Moreover, we discuss generalizations of this counting problem to several labels at the same time. We also study a refinement of the depth of the external node of rank \(s\), with \(0 \leq s \leq 2n\), by keeping track of the left, center, and right steps on the unique path from the root to the external node. The \(2n + 1\) external nodes of a ternary tree are ranked from the left to the right according to an inorder traversal of the tree. Finally, we discuss generalizations of the considered enumeration problems to embedded \(d\)-ary trees.