Context-free Grammars, Multivariate Stable Polynomials And Increasing Trees

The notion of the differential operator with respect to a context-free gram-mar was introduced by Chen. Chen proposed a framework of using context-free grammars to generate combinatorial polynomials. The theory of multivariate stable polynomials has been developed by Borcea and Branden. Based on their work, Haglund and Visontai presented a unified approach to the stability of the generating functions of Stirling permutations and r-Stirling permutations. More-over, Visontai and Williams gave some other results about stable multivariate Eulerian polynomials. The main object of this thesis is to use context-free gram-mars to get multivariate stable refinements of some combinatorial polynomials. Furthermore, we shall use grammatical method to derive combinatorial identities.This thesis is organized as follows. The first chapter is devoted to an intro-duction of the general background, the basic concepts and notations. Meanwhile, we will introduce the work of Haglund and Visontai on stability of the generating functions of Stirling permutations and r-Stirling permutations.In Chapter2, we will give an overview of differential operators associat-ed with context-free grammars. We will concentrate on how to use grammatical method to generate combinatorial polynomials and structures, especially for poly-nomials with multi-parameter.Chapter3is concerned with context-free grammars that lead to the sta-ble multivariate generating polynomials. Based on the characterization of sta-bility preservers for multiaffine polynomials given by Borcea and Branden, we will present an approach to proving the stability of polynomials generated by context-free grammars. At the end of this chapter we consider context-free gram-mars of the form G={fâ†'fb1+b2+1gα1+α2,gâ†'fb1gα1+1}, where ai and bi are integers subject to certain positivity conditions. Such a grammar G gives rise to triangular arrays{T(n, k)}0≤k≤n satisfying a three-term recurrence rela- tion. Many combinatorial sequences can be generated by such grammars. Let Tn(x)=∑nk=0T(n,k)xk. Based on the differential operator with respect to G, we define a sequence of linear operators Pn such that Tn+1(x)=Pn(Tn(x)). Applying the characterization on stability preserving linear operators on the multivariate polynomials due to Borcea and Branden, we obtain a necessary and sufficient condition for the operators Pn to be stability preserving. As a consequence, we are led to a sufficient condition for the real-rootedness of the polynomials defined by certain triangular arrays, obtained by Wang and Yeh. Moreover, as special cases of the grammar G, we obtain the Whitney grammar and the Bessel gram-mar, and we derive some identities involving the Whitney numbers and the Bessel numbers.Chapter4is devoted to showing that many combinatorial objects are cor-related with context-free grammars, and some properties can be got easily by using grammatical method. In this chapter we introduce a kind of special sub-stitution rules which we call it forbidding substitution rules. We will show how to use context-free grammars containing forbidding substitution rules to generate combinatorial objects and combinatorial identities.In Chapter5we will associate context-free grammars with urn models. We give analysis of the urn models related with context-free grammars which describe the consecutive132patterns in permutations and the isolated roots of strong n-restricted2-increasing forest.