A note on naturally embedded ternary trees

Details A note on naturally embedded ternary trees A note on naturally embedded ternary trees

2009-02-16

arxiv.org/abs/0902.2646v2

Mathematics

Combinatorics

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A note on naturally embedded ternary trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on naturally embedded ternary trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on naturally embedded ternary trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-462833