A note on naturally embedded ternary trees

Abstract

In this note we consider ternary trees naturally embedded in the plane in a deterministic way such that the root has position zero, or in other words label zero, and the children of a node with position $j$ have positions $j-1$, $j$, and $j+1$, for all $j\in \mathbb{Z}$. We derive the generating function of ternary trees where all nodes have labels which are less or equal than $j$, with $j\in \mathbb{N}$, and the generating function of ternary trees counted with respect to nodes with label $j$, with $j\in \mathbb{Z}$. Moreover, we discuss generalizations of the counting problem to several labels at the same time. Furthermore, we use generating functions to study the depths of the external node $s$, or in other words leaf $s$ with $0\le s\le 2n$, where the $2n+1$ external nodes of a ternary tree are numbered from the left to the right according to an inorder traveral. The three different types depths -- left, right and center -- are due to the embedding of the ternary tree in the plane. Finally, we discuss generalizations of the considered enumeration problems to embedded $d$-ary trees.

15 pages, 5 figures; Version 2: typos corrected, simplified formula for series $X$ added