On The Combinatorics Of Ramanujan Polynomials And Chapoton Polynomials

The main contribution of this thesis is combinatorics on Ramanujan polyno-mials and Chapoton polynomials. We give a new combinatorial explanation of the Ramanujan polynomials in terms of partially ordered increasing trees with the idea of context-free grammar, and establish a bijection between the two combina-torial interpretations of Ramanujan polynomials. We present a bijection between the two combinatorial interpretations of Chapoton polynomials in answer to a question posed by Guo and Zeng. Moreover, we give a combinatorial interpre-tation of the generating function of plane trees with respect to the number of younger children and the number of elder children obtained by Guo and Zeng in terms of dispositions, and establish a bijection between dispositions and plane trees in the spirit of Prufer correspondence. This gives an answer to a question of Guo and Zeng concerning a combinatorial interpretation of a refinement of Cayley’s formula. This bijection also provides an answer to another question of Guo and Zeng concerning an identity on the plane tree expansion of the Gessel-Seo polynomials. Some classical results can be reobtained under this bijection. By the construction of a bijection between dispositions and half-mobile trees, we manage to give a new combinatorial explanation of the Gessel-Seo polynomials.In Chapter1, we summarize the background knowledge on the Ramanu-jan polynomials, Chapoton polynomials, dispositions and context-free grammars. And we present some necessary definitions and preliminaries on permutations and trees.In Chapter2, we construct a bijection between the two combinatorial inter-pretations of Chapoton polynomials Qn,k(x,t) in answer to a question posed by Guo and Zeng, those are plane trees on [n] and plane trees on [n+1] with root1with respect to the number of younger children of vertex1and the total number of elder vertices. Also, we describe the correspondence (?) between the two inter- pretations of rQn-r,k(r,t), those are plane trees on [n-r+1] with root1and forests of plane trees with roots forming the smallest labels with respect to the total number of elder vertices.In Chapter3, we first give a combinatorial explanation of the disposition poly-nomials. Then we establish a bijection φbetween plane trees and dispositions, which gives an answer to a question of Guo and Zeng concerning a combinatorial interpretation of a refinement of Cayley’s formula. Some enumerative results on plane trees and rooted trees are also presented. Finally, we construct a bijec-tion between dispositions and forests of half-mobile trees, which provides another combinatorial explanation of the Gessel-Seo polynomials.In Chapter4, we establish a bijection between the two combinatorial struc-tures generated by Ramanujan grammar, those are rooted trees and partially ordered increasing trees, such that the number of improper edges in a rooted tree equals the number of marked edges in the corresponding partially ordered increasing tree.In Chapter5, we establish two bijections between the three combinatorial structures generated by Stirling grammar. One is a bijection between the set of Stirling permutations on [n]2with m ascents, l descents and k plateaus and the set of n-restricted increasing forests on [n]2with m non-leaf vertices,l non-root leaves and k trees with a single vertex. The other is a bijection between the set of increasing plane trees on [n] and the set of n-restricted increasing forests on [n]2.