tailieunhanh - Báo cáo toán học: "On the distribution of depths in increasing 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:On the distribution of depths in increasing trees. | On the distribution of depths in increasing trees Markus Kuba Institut fur Diskrete Mathematik und Geometrie Technische Universitat Wien Wiedner Hauptstr. 8-10 104 1040 Wien Austria kuba@ Stephan Wagner Department of Mathematical Sciences Stellenbosch University Private Bag X1 Matieland 7602 South Africa swagner@ Submitted Oct 28 2009 Accepted Oct 1 2010 Published Oct 15 2010 Mathematics Subject Classifications 05A19 05C05 60C05 Abstract By a theorem of Dobrow and Smythe the depth of the kth node in very simple families of increasing trees which includes among others binary increasing trees recursive trees and plane ordered recursive trees follows the same distribution as the number of edges of the form j j 1 with j k. In this short note we present a simple bijective proof of this fact which also shows that the result actually holds within a wider class of increasing trees. We also discuss some related results that follow from the bijection as well as a possible generalization. Finally we use another similar bijection to determine the distribution of the depth of the lowest common ancestor of two nodes. 1 Introduction Increasing trees are rooted labeled trees where the nodes of a tree of size n are labeled by distinct integers from the set 1 . n in such a way that the sequence of labels along any branch starting at the root is increasing. There are various important families of increasing trees such as binary increasing trees recursive trees or plane-oriented recursive trees. A general framework for these instances is given by what is known as simple families of increasing trees 3 such a family T is characterized by a sequence of non-negative THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R137 1 numbers Xfc fc 0 where Jo 0. This sequence is called the degree-weight sequence. We assume that there exists a k 2 with pk 0 to avoid trivialities. Now we assign a weight w T to any ordered tree T by w T ỊỊ v pd v where v ranges over all nodes of T