\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Markus Kuba}
%
%
\medskip
\noindent
%
%
{\bf A Note on Naturally Embedded Ternary Trees}
%
%
\vskip 5mm
\noindent
%
%
%
%
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\le s\le 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.
\end{document}