A note on naturally embedded ternary trees
| dc.creator | Kuba, Markus | |
| dc.date | 2009-02-16 | |
| dc.date | 2009-03-09 | |
| dc.date.accessioned | 2026-07-07T12:49:49Z | |
| dc.date.available | 2026-07-07T12:49:49Z | |
| dc.description | 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\Z$. We derive the generating function of ternary trees where all nodes have labels which are less or equal than $j$, with $j\in\N$, and the generating function of ternary trees counted with respect to nodes with label $j$, with $j\in\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. | |
| dc.description | 15 pages, 5 figures; Version 2: typos corrected, simplified formula for series $X$ added | |
| dc.identifier | https://arxiv.org/abs/0902.2646 | |
| dc.identifier | http://arxiv.org/abs/0902.2646 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/222502 | |
| dc.subject | Combinatorics | |
| dc.title | A note on naturally embedded ternary trees | |
| dc.type | text |