Some Studies About The Enumeration And Uniform Distribution Of Lattice Paths

Lattice paths of various types occupy an important position in combinatorics. On one hand, they serve as an important model to describe many combinatorial structures such as trees, pattern avoiding permutations, symmetric functions, orthogonal polynomials, continued fractions, etc. On the other hand, they often appear in other fields of mathematics including probability theory, statistics, etc. In this thesis, we mainly devote ourselves to studying the enumeration and uniform distribution of lattice paths of several types with the aid of vacillating tableaux, flaw lemma, etc.Oscillating tableaux and vacillating tableaux first appeared in the field of algebra. However, they are closely related to matchings and partitions which are the important research objects in combinatorics. Oscillating tableaux were first defined (though not with that name) by Berele in 1986. Stanley constructed a one-to-one correspondence between the set of oscillating tableaux of shape 0 and the set of matchings by using a version of the RSK algorithm, and the correspondence was extended by Sundaram in 1990. Vacillating tableaux were introduced by Halverson and Ram implicitly in 2005. In 2007, Chen et al. established a bijection between vacillating tableaux of shape (?) and partitions. As an application of this bijection, they solved an important problem in enumerative combinatorics. Roughly speaking, they proved combinatorially that the crossing numbers and the nesting numbers are distributed symmetrically over all partitions as well as over all matchings. Now, oscillating tableaux and vacillating tableaux have become a strong and useful tool in studying the properties and enumeration of partitions, matchings, etc.The well-known Chung-Feller theorem is a classical result in enumeration combinatorics, which is mainly about the uniform distribution of free Dyck paths on flaw number. This theorem was discovered by MacMahon in 1909, but named after the work of its re-discovers Chung and Feller in 1949 who proved the result by using analytic method. Over the years, this theorem has been extensively studied and proved in different ways. For example, Raney, Narayana, Rershowitz, Zaks, et al. used the cycle lemma or cyclic paths to prove the theorem respectively; Callan, Jewett, Ross, et al. proved it by establishing straightforward bijections respectively. Besides, the classical Chung-Feller theorem has inspired many generalizations and variations. For example, in 2001, Woan found another uniformly distributed parameter of free Dyck paths, i.e., absolute minimum length, and in the same year, Shapiro studied the uniform distribution of special Motzkin paths on absolute minimum length; Eu et al. gave a refinement form of the Chung-Feller theorem by using the Taylor expansions of generating functions, and they found a weighted version for free Schroder paths in 2005; Chen et al. derived the classical Chung-Feller theorem and the weighted version for free Schroder paths once more by introducing the butterfly decomposition of doubly rooted plane trees; Lately, Ma and Yeh did some work to study the uniform distribution of three classes of lattice paths on flaw number and absolute minimum length respectively.In this thesis, we mainly focus on studying the enumeration and uniform distribution of noncrossing free Dyck paths, m-free Schroder paths, partial k-free Dyck paths, etc. Our principal contributions are stated as follows.In Chapter 2, we obtain an enumeration formula for k-tuples of noncrossing free Dyck paths, which is based on the correspondence between k-tuples of noncrossing free Dyck paths and plane partitions with bounded size, and the enumeration formula of plane partitions given by Stanley. Restricting k to 2, we find the number is equal to that of noncrossing partitions with a given number of blocks which is due to Callan. With the aid of vacillating tableaux, we establish a one-to-one correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n + 1] with n + 1 blocks. Besides, in terms of Labelle merging algorithm, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths.In Chapter 3, on one hand, we do some work to study the uniform distribution of m-free Schroder paths on flaw number and absolute minimum length respectively. Our results unify and generalize the former studies on the Chung-Feller properties of free Dyck paths, k-free Dyck paths, free Schroder paths, etc. It is worth mentioning that we derive an intuitive but elegant lemma, named flaw lemma, in this thesis. This lemma can be viewed as a generalization of cycle lemma since it contains more information than the classical cycle lemma. Note that flaw lemma plays a crucial role in proving the uniform distribution of m-free Schr(?)der paths on flaw number. Moreover, we give an easier combinatorial proof for the enumeration formula of m-Schroder paths with a given number of diagonal steps. On the other hand, we find a new proof for the uniform distribution of free Dyck paths on absolute minimum length.In Chapter 4, we turn to study the enumeration of partial k-Dyck paths, and obtain another refinement form of the classical Chung-Feller theorem. Specifically, we get the uniform distribution of k-free Dyck paths with a given type on flaw number. Besides, a bijection between parking functions of length n and rooted forests on the vertex set [n] is given with the aid of labeled Dyck paths. Moreover, a sequence of enumeration formulae for noncrossing partitions, parking functions, and labeled forests follow.In Chapter 5, we adopt another viewpoint to re-consider the classical Chung-Feller theorem, that is, each free Dyck path is seen as a lattice walk from the origin and back to the origin with the step (1,0) or (-1,0). It makes us be able to find and prove two interesting Chung-Feller properties about two classes of lattice walks in a quarter of plane.