tailieunhanh - Báo cáo toán học: "A note on naturally embedded ternary trees"

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 .