Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A note on naturally embedded ternary trees. | A note on naturally embedded ternary trees Markus Kuba Institut fur Diskrete Mathematik und Geometrie Technische Universitat Wien Wiedner Hauptstr. 8-10 104 1040 Wien Austria kuba@ Submitted Feb 3 2009 Accepted Jul 1 2011 Published Jul 15 2011 Mathematics Subject Classification 05A15 05C05 Abstract 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 G 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 G 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 s 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. Keywords Ternary trees Embedded trees Labeled trees 1 Introduction The study of tree families embedded in the plane has recently received a lot of attention. Binary trees complete binary trees families of plane trees and more generally simply generated tree families have been considered in a series of papers 5 6 17 10 3 2 15 16 9 19 11 12 . It has been shown that embedded trees are closely related to a random measure called ISE Integrated SuperBrownian Excursion . For example in the recent The author was partially supported by the Austrian Science Foundation FWF grant S9608-N13. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 p142 1 paper of Devroye and .
