The Applications Of Probabilistic Methods And Context-free Grammars In Permutation Statistics

Enumerative combinatorics is an important branch of discrete mathematics,its research field has close relations with group theory,geometry,graph theory,topology and operational research.Enumerative combinatorics mainly studies the enumeration of finite structures,it grows quickly with the flourish of computer science.Permutation statistics is an important component of enumerative combinatorics,at the prompting of many Mathematicians such as D.Foata,R.P.Stanley,W.Y.C.Chen,the theory of permutation statistics establish tight relations with trees,symmetric function,Young tableaux,lattice path,etc,thus the study of permutation statistics is of great theoretical significance.In this paper,we mainly study the polynomials of permutation statistics such as alternating runs and peaks,we also study derangement polynomials.The paper is arranged as following:In chapter one,we introduce background and the recent study of studying of permutation statistics by using probabilistic methods and context-free grammars.We also introduce the basic methods.In chapter two,we mainly study the enumeration of permutation statistics like alternating runs,interior peak and left peak,and get their expections and varience.In chapter three,we give context-free grammars to permutation statistics with common type recurrence relations of order three.We also give combinatorial explanations to the context-free grammars of some permutation statistics,such as the derangement polynomials of type A and B.In chapter four,we summarize the main results of the paper,and pose three problems for readers to study.