Riordan矩阵与Riordan群在组合数学中的应用研究

A Riordan matrix (or Riordan array) is a special type of infinite lower triangular matrix defined by two formal power series, and the generating function of each column of this matrix is determined by these power series. The set of all Riordan matrices forms a group called the Riordan group. For instance, the so-called Pascal matrix and Catalan matrix are all special cases of Riordan matrices. In Combinatorics, the applications of Riordan matrices are to characterize combinatorial problem and to prove combinatorial identities. Among other applications Riordan matrices turned out to be an extremely powerful tool in dealing with combinatorial identities. Sprugnoli have used Riordan matrices to find several combinatorial sums in closed form and also to determine their asymptotic value. Additional applications of Riordan matrices are to the evaluation in closed form of sums involving binomial, Stirling, Bernoulli and harmonic numbers. The Riordan matrix technique has also been employed to show that two combinatorial sums are equivalent, regardless of whether they have a closed form expression or not. Formally, Riordan matrices are a formulation of the 1-Umbral Calculus, as defined by Roman, although their name was only coined later in 1991 by Shapiro. Because of that, Riordan group has a tight connection with the Sheffer group. . In this project, we intend to study the Riordan matrices, Riordan group and their applications in Combinatorics. The main object of the project is as the following. By establishing the correspondence between Riordan matrices and combinatorial problems, we will classify the combinatorial problems according to subgroups of the Riordan group and then we study each type of the problems. In addition, we will investigate the enumeration of colored lattice paths in some given restricted conditions, especially the enumeration of colored Lukasiewicz paths and the relationship between the Lukasiewicz paths and other combinatorial structures. Finally, we will explore the connection of Bell polynomials and Riordan matrices as well as the the connection of Sheffer sequences and Riordan matrices, we also consider the combinatorial interpretation for the Bell polynomials and Sheffer sequences.. We shalll show how to use Riordan matrix to count the number of colored lattice paths which avoid a set of forbidden patterns. We will also show how to use ECO method to generate Lukasiewicz paths with a given pattern, develop a method of constructing new Riordan matrices from a given one, and study the enumerative interpretations of central coefficient matrices and half matirx of a given Riordan matrix. For every question, we will give several concrete examples, find an explicit formula or generating function of enumerative sequence, derive exhaustive generating algorithms for the enumerative objects by ECO method, and explore links between the Riordan matrices and the combinatorial objects.

一个Riordan矩阵是由两个形式幂级数确定的无穷下三角形矩阵，这个矩阵的每一列的发生函数由这两个形式幂级数完全确定。全体Riordan矩阵的集合关于矩阵的乘法运算构成一个群, 称之为Riordan群。在组合数学中，Riordan矩阵的主要作用是刻划组合问题以及证明组合恒等式。本项目的主要研究内容为: 通过建立Riordan矩阵与组合问题之间的联系, 利用Riordan群的子群对组合问题进行分类研究; 研究在限制条件下着色格路特别是Lukasiewicz路的计数问题以及Lukasiewicz路与其它组合构型的关系；研究Bell多项式与Riordan矩阵之间的关系, Sheffer序列与Riordan矩阵的关系以及Bell多项式和Sheffer序列的组合意义; 研究Riordan矩阵的中心系数矩阵、取半矩阵的刻画及其组合解释；应用ECO方法和生成树从组合角度寻求Riordan 矩阵的刻划。

一个Riordan矩阵是由两个形式幂级数f(t)和g(t)确定的无穷下三角形矩阵，其中第k列的生成函数为g(t)与f(t)的k次幂的乘积。全体Riordan矩阵的集合关于矩阵的乘法运算构成一个群, 称之为Riordan群。本项目通过建立Riordan 矩阵与组合问题之间的联系，研究了在一定限制条件下格路的计数问题，特别是Dyck路、Motzkin路、广义Catalan路、以及Lukasiewicz路的计数问题以及这些路径与其它组合构型的关系; 研究了Riordan 矩阵的中心系数、半Riordan矩阵、中心Riordan矩阵的刻画及其组合解释；利用Riordan矩阵给出了阶乘数、广义阶乘函数的Hankel行列式的计算方法; 给出了Catalan 矩阵的一种统一形式，并且研究了Catalan矩阵的分解及其应用；引入了(m,r)-中心Riordan阵的概念，并用这一概念研究了几类着色Motzkin路计数问题；利用加权Motzkin路给出了一类矩阵恒等式的组合解释，并且得到了一些新的恒等式；研究了Pascal 菱形的组合解释，引入了含参Pascal 菱形的概念，并用这一概念研究了几类加权Schroder路的计数问题。