The Application Of Combinatorial Transformations On Identities, Polynomials And Simple Graphs

There has been a focus of interest in exhibiting some mathematical problems elegantly and intuitively by virtue of combinatorial methods.The essence of the combinatorial methods is to construct the combinatorial settings and find the appropriate combinatorial transformations.In this thesis,on one hand,we will apply this idea to the identities of Simons and Munarini in order to explain these identities combinatorially.The combinatorial technique for the Munarini identity can be also used to explore the Boros-Moll polynomials coefficients' positivity. On the other hand,as another application of combinatorial transformations,this thesis verifies that the crossing number and nesting number have a symmetric joint distribution over an involved class of simple graphs.The Simons identity is a binomial coefficient identity,which was established by Simons via repeated differentiation.This identity has been proved by Chapman using the generating functions,by Prodinger using the Cauchy integral formula, and by Wang and Sun using an operator method.Hirschhorn pointed out that the Simons identity is in fact a special case of the Pfaff identity on ₂F₁ hypergeometric series,which has been given a combinatorial interpretation by Labelle and Yeh.By constructing a combinatorial transformation on two kinds of weighted combinatorial structures-weighted free Dyck paths and weighted free Schr(o|¨)der paths,this thesis presents a more visual and intuitive interpretation of the Simons identity.Munarini follows the approach of Prodinger to obtain the generalization of the Simons identity,that is,the Munarini identity,which is also a generalization of the Pfaff identity.Moreover,Shattuck provided elementary bijective proofs for some special cases of the Munarini identity.Employing the technique developed by Labelle and Yeh for the Pfaff identity,we exhibit a combinatorial interpretation of the Munarini identity.This thesis also explores the Boros-Moll polynomials coefficients' positivity combinatorially.The Boros-Moll polynomials,which are closely related to a special class of Jacobi polynomials,arise in the evaluation of a quartic inte- gral.Amdeberhan and Moll gave several proofs for the expression of this class of polynomials.Boros and Moll have proved the Boros-Moll polynomials coefficients' positivity by using Ramanujan's Master Theorem.In addition,there are some other combinatorial properties on the coefficient sequence of the Boros-Moll polynomials,e.g.unimodality and log-concavity.Revealing these properties in a combinatorial way has been an interesting direction.The study of the symmetric joint distribution of crossings and nestings in a class of simple graphs is another application of combinatorial transformations in this thesis.In 1983,De Sainte-Catherine proved that 2-crossings and 2-nestings are identically distributed over all matchings of[2n].Later,Klazar extended this result by showing that the number of matchings with r 2-crossings and s 2-nestings is equal to the number of matchings with r 2-nestings and s 2-crossings. Recently,there has been a revival of interest in the crossing and nesting of graphs related to their symmetric joint distribution.In 2007,based on the RSK algorithm, Chen et al.proved that the crossing number and the nesting number have a symmetric joint distribution over all set partitions of[n],as well as over all matchings on[2n],which is also deduced by Krattenthaler via filling of Ferrers diagram.This thesis generalizes this result by constructing a new algorithm, namely,the modified RSK algorithm.In this thesis,we will discuss the application of combinatorial transformations in two aspects.One is to give combinatorial explanations of the identities of Simons,Munarini and the Boros-Moll polynomials coefficients' positivity.The other is to confirm the symmetric joint distribution in the simple graphs with the left degree of each vertex no more than 1.Our main contributions in this thesis are stated as follows.Chapter 2 concerns our first main results,i.e.,the combinatorial explanations of the identities of Simons,Munarini and the Boros-Moll polynomials coefficients' positivity.The combinatorial transformation for the Simons identity is based on free Dyck paths and free Schr(o|¨)der paths,and an involution on weighted free Schr(o|¨)der paths.Meanwhile,the combinatorial transformations for the Munarini identity and the Boros-Moll polynomials coefficients' positivity are based on a correspondence of Foata and Labelle between the Meixner endofunctions and bi- colored permutations,and the technique developed by Labelle and Yeh for the Pfaff identity.Chapter 3 and Chapter 4 will present our second contribution.In Chapter 3,we introduce the modified RSK algorithm.By utilizing this algorithm,we construct a one-to-one correspondence between the words w in an ordered alphabet and the ordered pairs(P(w),Q(w))of tableaux with certain restrictions. Moreover,we show that the length of the longest increasing subsequence of w equals the number of columns of P(w),while the length of the longest decreasing subsequence of w equals the number of rows of P(w).Based on the modified RSK algorithm in Chapter 3,Chapter 4 contributes to the symmetric joint distribution of crossing number and nesting number in the simple graphs with the left degree of each vertex at most 1.This result is achieved by a bijection between the involved simple graphs and active-vacillating tableaux of empty shape.In fact,our result still holds for fixed lefthand endpoint set and righthand endpoint set.