Combinatorics Of Increasing Trees And K-dimensional Increasing Trees

An increasing tree,also called a recursive tree,on the vertex set [(?)] = {0,1,...,n}is a rooted tree on the vertex set [(?)] for which the labels of the vertices along any path from the root to a leaf are increasing.Increasing trees have been widely studied from the point of views of combinatorics and probability.The main objective of this thesis is to investigate the combinatorics of increasing trees and k-dimensional increasing trees.There are four chapters in this thesis.In Chapter 1,we provide some basic definitions and some relevant results that will be used in the thesis.In Chapter 2,we first introduce a general method to construct bijections on increasing trees.Next,by using this general method we construct an involution on increasing trees,which sends the set of odd vertices to the set of even vertices at odd levels,and sends the set of even vertices at even levels to itself.Finally,we give some applications of this involution,including:(a)we show that the statistics “the number of odd vertices”and “the number of even vertices at odd levels” are equidistributed;(b)we give a new combinatorial interpretation for the secant numbers;(c)we show that the expectation of the random variable that counts the number of even vertices is twice the expectation of the random variable that counts the number of odd vertices in random recursive trees.In Chapter 3,we introduce the notion of perfect orientations of increasing trees.By using our general method for constructing bijections on increasing trees proposed in Chapter 2,we construct a class of perfect orientations of increasing trees.This leads to a novel technique,called the “oriented technique”,for dealing with vertex degrees of increasing trees and random recursive trees.For increasing trees,using the oriented technique,(a)we give a simple proof of a theorem due to Kuznetsov,Pak and Postnikov on Euler numbers,we also obtain a “dual” result of it;(b)we obtain four new combinatorial interpretations for the classical Eulerian numbers.For random recursive trees,we give two examples to illustrate that the oriented technique can be used to compute the expectations of certain random variables in random recursive trees,one of which gives a simple form for the Dondajewski-Szyma (?)ski formula.In Chapter 4,we introduce the concept of k-dimensional increasing trees.In particular,a 0-dimensional increasing tree consists of several isolated vertices;a 1-dimensional increasing tree is an ordinary increasing tree;a 2-dimensional increasing tree is essentially an increasing plane tree.We build a bijection between k-dimensional increasing trees and k-Stirling permutations,and a bijection between k-dimensional increasing trees and k-trapezoidal words.Some enumerative results are proved by using the two bijections.As an application,we find three statistics of trapezoidal words [1] × [3] × · · · × [2n-1] that correspond to the number of ascents,the number of descents and the number of plateaux of Stirling permutations respectively;this problem was suggested by Janson [39].As another application,we obtain some new combinatorial interpretations for Catalan numbers and Catalan's triangle.Moreover,we give a new combinatorial interpretation for the kth-order Eulerian numbers using k-dimensional increasing trees.