Statistics On Some Varieties Of Trees

The enumeration of trees is a subject with a long history in combinatorics. Until recent decades, it is still an active area. Trees are important combinatorial structures in various areas, such as combinatorics, computer science, computa-tional biology as well as mathematical physics. Formally, a tree can be defined as a simple connected graph without cycles. The main objective of this thesis is to utilize some tools to solve problems about the statistics of different kinds of trees and to establish the connection between trees and some other combinatorial structures, including mappings and permutations. Firstly, we use rooted trees to provide a combinatorial proof of a conjecture posed by Lacasse in his study of the classical PAC-Bayes theorem in the theory of machine learning. Secondly, we introduce k-dominant trees and give a bijection between k-dominant trees and k-Stirling permutations, which solves an open problem posed by Janson, Kuba and Panholzer [34]. Thirdly, we define marked plane recursive trees and give two proofs of equidistribution between marked plane recursive trees and series-reduced trees grammatically and bijectively. Finally, we develop a class of augmented grammars, which can be used to study pattern-avoiding combinatorial structures.The organization of this thesis is as follows. The first chapter is devoted to an introduction of basic notations and definitions. We first give a brief review of the basic notations of trees, including varieties of trees and statistics in trees. Next we recall the notions of n-mapping and permutations. Finally, we pose a quick review of context-free grammars, which is introduced by Chen [8] as a tool of studying combinatorial structures by utilizing formal calculations.In Chapter2, we give a decomposition of triply rooted trees into three doubly rooted trees through the operation of merging on trees, with which we provide a combinatorial proof of a Lacasse’s conjecture. Next, we introduce a bijection between triply rooted trees and augmented n-mappings, with which we obtain a refinement of the Cayley’s formula. This bijection also preserves some interesting statistics. Based on the property of our bijection, we deduce a symmetry property of augmented n-mappings with respect to the number of periodic points and the size of the orbit of n+1. In the end of this section, we obtain a formula for the number of augmented n-mappings in which there are i periodic points and the size of orbit of n+1is j.In Chapter3, two notions of k-dominant trees is introduced, which can be seen as a specification of k-plane recursive trees. As a refinement of a grammar introduced by Chen and Fu [10] to generate the generating functions of descents of k-Stirling permutations, we introduce a refined grammar who also marks as-cents and plateaux of k-Stirling permutations. Furthermore, we prove that the grammar can also be used to generate k-dominant trees, which builds the e-quidistribution of k-dominant trees and k-Stirling permutations. Next, we give a bijective proof of the equidistribution, which solves the problem of Janson, Kuba and Panholzer.In Chapter4, we introduce a notion of marked plane recursive trees. Sur-prisingly, we find the new structure can be generated by the same context-free grammar as series-reduced trees. This grammar is called Schroder grammar. Un-der this grammar, we find the number of inner vertices in series-reduced trees is equidistributed to the number of unmarked non-root vertices in marked plane re-cursive trees. Next we consider a pair of reciprocal operations,"contraction" and "splitting", and construct a Injection between series-reduced trees and marked plane recursive trees preserving the above equidistribution.In Chapter5, a general method for studying context-free grammars is provid-ed. Precisely, for a context-free grammar G, we define the augmented grammar G of G and deduce a relation between G and G. Next, we apply our method to obtain some interesting properties of0-1-2increasing trees and cycle up-down permutations. On one hand, We prove that the number of0-1-2increasing trees on [n+1] containing no minimal vortices with degree one equals the number of cycle up-down derangements on [n]. On the other hand, we provide an interesting combinatorial interpretation of the sequence A003701in OEIS by means of cycle up-down permutations.