符号化方法与格路计数

The symbolic method, introduced by P. Flajolet and R. Sedgewick to compute (ordinary, exponential, and multivariate) generating functions in a systematic way, makes use of basic objects and some construction rules to combine them in order to obtain more complex objects of the same kind so that their generating functions are computed in a way that reflects these combinations. In general, the symbolic method is the standard tool to derive a functional equation on generating functions. By expanding generating function into formal power series ，or by Lagrange inversion formula, we can obtain the counting sequences and their asymptotic behavior. The importance of symbolic method can be seen in the vast amount of available literature, especially it has proved to be useful and applicable for lattice path combinatorics. The enumeration of lattice paths is a classical topic in combinatorics which is still a very active field of research. Its fascination is founded in the fact, that despite the easily understood construction of lattice paths, most of their properties remain unproven or even unknown. The main motivation to study lattice paths lies in the richness of applications. Indeed, lattice paths are related to many combinatorial objects. For example, maps, permutations, trees, Young tableaux, and many other combinatorial objects can be encoded by lattice walks, in particular by walks in the quarter plane. Moreover, lattice paths are also related to population biology, as the quarter plane is the natural space to parametrize any two-dimensional population; probability theory, since random walks in cones (e.g., quantum random walks, non-colliding random walks) are a very actual topic; queueing theory, as any two-dimensional queue can be modeled by random walks in the quarter plane. . The main aim of this project is as following. By using symbolic method, we will study enumerations of generalized Schroder paths and computation of many generating functions related to several statistics; enumerations of strings in Lukasiewicz paths and the distrubitions of several combinatorial statistics; computation of area under a generlized Dyck path; enumerations of Motzkin paths in a band, and enumerations of restricted random walks. We will investigate certain directed paths, which are walks with one fixed direction of increase, and we will show the connections to the theory of linear recurrences. In addition, we will investigate the relationship between the Lukasiewicz paths and other combinatorial structures, such as ordered trees and permutations. Finally, we will explore the connection between bivariables generating functions for some classes of combinatorial objects and Riordan arrays.

符号化方法是研究组合数学问题的一个有力工具。从组合对象的生成规则出发，找到其形式语法，通过符号化方法就能够直接获得组合对象的生成函数。然后把生成函数展成形式幂级数,应用拉格朗日反演公式或复分析方法就能够得到组合对象的计数序列的组合性质或渐近行为。格路是一种离散数学模型,在组合计数、概率统计、粒子物理等领域有广泛的应用。二维平面上的格点组成的有限序列叫做格路。格路上相邻两点构成的向量叫做步。经典的格路问题主要研究在给定步集和一定的边界条件下的格路的计数问题以及格路与其它组合构形（如平面树、置换、杨表等）的对应关系。本项目拟用符号化方法研究几类格路计数问题，主要研究内容为：广义Schroder路的计数问题以及多种统计量的计算；Lukasiewicz路与其它组合对象的关系以及各种统计量的分布；广义Dyck路与轴线所围面积问题；平面上带状区域内的Motzkin路的计数问题以及随机游动问题。

符号化方法是组合数学中建立生成函数所满足的方程的一种综合性方法。通过把生成函数展成幂级数或者利用Lagrange反演公式，我们能够得到组合序列的显式公式或其渐近性质。格路是指由空间的格点组成的长度有限的序列，其相邻两点构成的向量叫做步。格路可以用构成它的步组成的字符串来表示。格路非常适合用于表示各种组合构型及其特性，所以很多领域的问题可以通过解决格路问题而得到解决。 . 本项目用符号化方法和Riordan矩阵研究了几类格路计数问题和有序树的计数问题。我们研究了一类广义加权Delannoy路,得到了相应的广义Schroder路上的Chung-Feller性质,得到了加权Schroder路和加权Motzkin路的关系。我们利用m-Schroder路的计数引入了m-Schroder数的概念, 并研究了相关的组合问题以及m-Schroder矩阵的组合性质。我们研究了步型为无限的一类格路计数问题, 得到了具有无限步型的这类格路上的Chung-Feller性质。我们利用Riordan矩阵刻画了Lukasiewicz路上的若干组合结构, 得到了广义Narayana多项式的组合意义, 建立了加权Lukasiewicz 路和加权Schroder路之间双射对应关系, 得到了Schroder数的一种新的组合解释。我们引入了有序树上的弱保护点的概念，研究了弱保护点的分布，研究了有序树的保护分支，研究了混合二元树的一些计数问题。