Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Descendants in increasing trees"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Descendants in increasing trees. | Descendants in increasing trees Markus Kuba Institut fur Diskrete Mathematik und Geometrie Technische Universitat Wien Wiedner Hauptstr. 8-10 104 1040 Wien Austria E-mail Markus.Kuba@tuwien.ac.at Alois Panholzer Institut fuur Diskrete Mathematik und Geometrie Technische Universitaut Wien Wiedner Hauptstr. 8-10 104 1040 Wien Austria. E-mail Alois.Panholzer@tuwien.ac.at Submitted Jul 20 2005 Accepted Jan 19 2006 Published Jan 25 2006 Mathematics Subject Classification 05C05 Abstract Simple families of increasing trees can be constructed from simply generated tree families if one considers for every tree of size n all its increasing labellings i. e. labellings of the nodes by distinct integers of the set 1 . n in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest recursive trees plane-oriented recursive trees and binary increasing trees. We study the quantity number of descendants of node j in a random tree of size n and give closed formula for the probability distribution and all factorial moments for those subclass of tree families which can be constructed via an insertion process. Furthermore limiting distribution results of this parameter are given. 1 Introduction Increasing trees are labelled trees where the nodes of a tree of size n are labelled by distinct integers of the set 1 . n in such a way that each sequence of labels along This work was supported by the Austrian Science Foundation FWF grant S9608-N13. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R8 1 any branch starting at the root is increasing. As the underlying tree model we use the so called simply generated trees see 7 but additionally the trees are equipped with increasing labellings. Thus we are considering simple families of increasing trees which are introduced in 1 . Several important tree families in particular recursive trees plane-oriented recursive trees also called heap ordered trees or .