格路计数问题的研究与进展

The Research and Progress of the Enumeration of Lattice Paths

格路计数是一种重要的组合计数模型,由于在不同学科的离散结构研究中能提供强大的方法和技术支持,所以备受关注,是研究的热点.本文综述在维数、步、起点终点位置等限制条件影响下的单条格路和多条不相交格路簇计数模型及其应用.(1)介绍Dyck格路等经典格路及格路计数的一些研究进展;(2)介绍利用生成函数研究格路计数问题的一种方法;(3)介绍利用矩阵研究格路计数问题的一些方法;(4)介绍格路簇计数问题及一些计数方法;(5)介绍不相交格路簇计数模型在对称函数论中的应用,并列出了一个有关的公开问题.

The enumeration of lattice paths is an important counting model in enumerative combinatorics.Because it can provide powerful methods and technical support in the study of discrete structural objects in different disciplines,it has attracted much attention and is a hot research field.In this paper,we summarize two kinds of the lattice path counting models that are single lattice paths and family of nonintersecting lattice paths,and their applications in terms of the change of dimensions,steps,constrained conditions,the positions of starting and end points,and so on.(1)The progress of classical lattice paths such as Dyck lattice is introduced.(2)A method to study the enumeration of lattice paths problem by generating function is introduced.(3)Some methods of studying the enumeration of lattice paths problem by matrix are introduced.(4)The family of lattice paths problem and some counting methods are introduced.(5)Some applications of family of lattice paths in symmetric function theory are introduced,and a related open problem is listed.