Permutation Statistics And Chen’s Context-free Grammars

Enumerative Combinatorics mainly deals with the enumeration problem of finite discrete objects,and is closely related to Graph Theory,Number Theory,Algebraic Topology,Probability Theory and other mathematical branches.It also has significant applications in other natural sciences.In particular,it provides a theoretical basic knowledge for the calculation of discrete probability and algorithm design in computer science.Permutation statistics is one of the core objects in the study of Enumerative Combinatorics,and its modern research originated from the work of British mathematician MacMahon.French combinatorist Foata applied combinatorial bijection to study the same distribution of permutation statistics,and Chen Yongchuan,academician of Chinese Academy of Sciences,introduced context-free grammar to formally calculate permutation statistics.Gamma positivity of polynomials is a powerful tool to deal with unimodal problems and contains abundant combinatorial properties.This thesis mainly studies the simple application of Chen’s context-free grammars on permutation statistics and the combinatorics of multiset Eulerian polynomials’ gamma positivity.The main contents are divided into the following two parts.The first part studies some applications of Chen’s context-free grammars in permutation statistics.Firstly,we introduce the basic definition and properties of grammar,and demonstrate the application of the idea of grammar in proving classical identities in combinations.Then,we generate the Eulerian polynomials by using the grammar labeling method and calculated its exponential generating function.The gamma positivity of Eulerian polynomials is further discussed by using the grammar transformation method.Finally,we study the grammar labeling of three different mountain statistics and get the corresponding recurrence relation and exponential generating function of Peak-polynomials.The second part studies the combinatorics of the gamma positivity of multiset Eulerian polynomials.First,we give a new class of Eulerian polynomials with bi-gamma positivity,and provided an algebraic proof and a simple combinatorial proof.This work generalizes the bi-gamma positivity results obtained by Ma Shimei,Ma Jun and Ye Yongnan using Chen’s context-free grammars.Then,we give the combinatorial interpretation of gamma coefficients of p-multiset Eulerian-polynomial for the first time.This addresses an open question recently raised by Lin Zhicong et al.Finally,we find the recurrence relation of Eulerian-Narayana numbers on general multiset by using the decomposition of weakly increasing tree and Lagrange-inversion formula.