1. 引言
Catalan数有着非常丰富的历史背景，是组合数学中一类使用广泛，拥有众多组合意义的组合数，常用来解决在各类组合计数问题。一般记为。其名字来源于18世纪比利时的数学家Eugene Charlie Catalan。其在1838年研究Catalan问题：不满足乘法结合律的n个因子的乘积，在保持因子顺序的结合数？最终获得了Catalan数的显性表达式：
。
Cn是该数列的第n + 1项。这是贾宪三角中垂线上的数依次除以其相对应的自然数之后所得一个数列。其与Fibonacci sequence，Stirling数一起作为组合数学之中的典型例子。但实际上卡Catalan并不是第一个研究Catalan数的数学家。在十七世纪三十年代时，我国清代数学家明安图在研究无穷级数时得到了Catalan数的三种不同算法 [1] ，并作为计算特定级数的方法在之后的研究中使用，建立了一个暗含了Catalan数的几何模型 [2] 。其中有两个算法公式在当代的组合数学书籍以及论文之中都没有涉及到。有关于明安图计算无穷级数时所得的一系列结果都详细记载在《割圆密率捷法》中，在这一本书中给出了Catalan数的卷积型递推公式为
其中另一个重要的公式是获得Catalan数的组合型递推公式
在这之后不久的1758年，大数学家欧拉与赛格纳讨论这么一个问题：用一个凸多边形彼此之间不相交的对角线把凸多边形划分成若干个三角形区域的方法数。针对于此问题，划分n + 1条边的多边形的方法数就是Catalan数。而之后的董祐诚等清代数学家受明安图的影响下，对Catalan数都做出了一定的研究成果，其研究时间都早于Catalan研究Catalan数。之后比较值得注意的是1839年Bi Noto，其通过一系列证明，最终推出了Catalan数的生成函数的表达式：
从上文可以知道，Catalan数最早并不是Catalan提出的，但由于一种习惯或约定，现在已经变成数学名词。
在19世纪，数学家们得到两个Catalan数的递推公式：
随着越来越多的数学家研究Catalan数，在越来越多的领域里发展和拓广Catalan数的应用和新的组合解释，如：非结合代数问题、随机游动问题、图形剖分问题、特定非负整数解问题、出栈问题、几何、代数问题，网格路径等组合解释。初步估计下来应该在200种以上，他们散落在各种文献之中。初文昌在《关于Catalan序列》一文中给出了25种不同的组合解释 [3] 。
近年来，对于Catalan数的研究主要是得到了Catalan数各种拓广形式和其相对应的枚举结果。主要是以下几个方面的：高阶Catalan数、广义Catalan数 [4] 、连续q-模拟、Catalan数的同余(或整除)性质，二项式系数问题 [5] ，Motzki数 [6] ，Riordan群 [7] 等方面等。本文的主要工作就是利用Catalan数与生成函数法来解决一类特殊数学结构的计数问题，构造出该数学结构解的显性表达式。最后还给出了该数学结构计数问题的另一种解决方案，从另一个角度也利用了广义的Catalan数来解决问题。
2. 一个广义Catalan数问题
问题1：
关于该数学结构计数问题，是一类广义Catalan数问题，涉及到线性不等
式组的整数解以及整数规划问题。是一类特定非负整数解问题。现在能在网上找到的解答都是在已知结果的情况下，运用数学归纳法来解决的。其前提都是在已知解结构的情况下来完成的。但并不知道这个解是怎么来的。接下来将用两种不同方法来构造出该数学结构具体解的形式。它们分别涉及网格路径法、生成函数法两种不同的数学方法以及广义Catalan数。在求解该数学机构计数问题过程之中，可以领悟到Catalan数运用的广泛性及其深刻性。
3. 预备知识
先给出在之后的证明过程中需要的一般概念，定义和相关结论。
生成函数法的思想其实就是让幂级数与离散的数列一一对应，把数列中的第n项与幂级数中指数为n的项相对应起来，再利用幂级数的运算性质去确定离散数列的结构。
定义1. 对于一个有限或无限的序列 [8]
称为的生成函数，称为的指数型生成函数。
定义2.不满足乘法结合律的n个因子的乘积，在保持因子顺序的情况下，有种结合方法。这里的就等于Catalan数序列中的第n项。
以Catalan数为系数的形式幂级数的和为。
引理1. 网格图中从点到点()的最短路径数为
证：从网格的任一结点处向上走一格记为y；向右走一格记为x；那么，从点O走到点M要向上走b格，向右走a格。从点O到点M的每一条最短路径都对应一个由a个x和b个y组成的长为的字，且两者是一一对应的。因此，只需要在个字母中指出哪a个是x (或哪b个是y)就对应一条最短路径。所以，
引理2. 网格图中从点到点()的最短路径满足的路径数为
证：等于从点到点的最短路径减去从点A到点M穿过直线的最短路径数。后者又与从点到点M的最短路径数相等。即
有关的组合恒等式：
4. 生成函数法解决
这里的话，要先试着去找出它的边界条件和递推关系式来。
先就的取值进行一个讨论
1) 若，则问题转化为求，
2) 若，则原问题转化为
从而问题可转化为。
综合1)，2)可以得到这样一个关于的递推关系式。
但这时边界条件还没有得到。接下来，来找到的边界条件，就，分开讨论，得出其所对应的边界条件。
3) 当时，原问题可转化为；此时解的个数相当于从这个数中选出一个数的种数。故。
4) 当时，原问题可转化为
又等价于
来思考其几何意义，其表示从网格图上点出发达到直线上的各点最短路径数(满足)的和。又根据引理2：网格图中从点到点()的最短路径满足的路径为。
故根据定义我们可以得到的计算公式
5) 当m = 1时，原问题可转化为
这与4相似，类比4得到：
6) 现知的递推关系式
边界条件；；。
下面利用生成函数法来解出该递推关系式。
构造一个二元幂级数
(1)
根据边界条件，时的的表达式是已知的，故把其分成和两种情况来分开计算
(2)
同样是根据边界条件，时的的表达式是已知的，故把与两种情况也分开计算
(3)
其中为了方便计算把(3)式中的第三项单独拿出来，进行变形化简之后再放回(3)式中进行计算
(4)
将的递推关系式代入(4)中可得
(5)
先将(5)中第一项的式子里提出一个，第二项里提出一个，使得中n，m可以与x，y的指数相互对应起来得到
(6)
通过改变指标的取值范围，可以将与x，y的指数相互对应起来得到了
(7)
由(1)式的关系，把(1)进行适当的拆分，移项后，可以得到：
将这两个式子带入到(7)中代替第一项和第二项化简后可以
(8)
适当改变n，m的取值范围，变形(8)式，可以得到下面这样一个式子
(9)
将(9)式带入到(3)式之中去，已知
又；。
我们将其代入后计算可以得到：
化简后的(3)式为
(10)
将代入(10)式
(11)
又(1)式等于(11)式，我们将其相等后化简可得下式：
(12)
在这里为Catalan数，根据已知的结论，
将其带入到(12)式之中，可得到
(13)
运用泰勒展开公式
；
则(13)式展开后变形化简之后，可得到下式
(14)
根据生成函数的理论可知
至此该数学结构解的个数就被我们所构造出来了。在这之中运用了广义Catalan数来帮助进行计算，体现了Catalan数应用的广泛性，在这里使用生成函数法，给出了的一个显式的表达式。在这里的关键是能够把这一序列与生成函数建立一个一一对应，然后再利用生成函数的性质和运算，得到另一个序列，从而两个序列相比较得到了的表达式。现在已经用生成函数法得到了该数学结构的计数的显性表达式，但这个过程中也发现了，计算比较的繁琐，接下来将通过解析该数学结构的几何意义后，通过网格路径法来给出一种完全不同的解决方案。
5. 网格路径法解决问题
我们现在来思考一下问题1的几何意义。先来再看一次这个不等式组
从上到下来开，从原点出发，左式每加上一个xi，就向右移动一个单位，向上移动个单位。那么最终来看就是向右移动了个单位，向上移动了个单位。在做了这样的转换之后，得到了下面这样一个等价问题：
网格图中从点到上各点()的最短路径经过任一节点时，满足(即路径与直线)的路径数的和为。
定理1. 记网格图中从到点()的最短路径经过任一节点时，满足(即路径不穿过直线)的路径数 [9]
证明：从点到点的不穿过直线的最短路径数等于从点到点的最短路径数减去从点O到点M穿过直线的最短路径数。后者又等于从点到点的最短路径数减去从点O到点M碰到或穿过直线的最短路径数。
下面建立从点到点的最短路径数减去从点O到点M碰到或穿过直线的最短路径(记做)与从点到点M的最短路径(记做)之间的一一对应关系。
设与的第一个交点为P，从点O到点P的这段路径OAP关于直线的对称路径记为，以代替OAP得到从点到点M的一条路径。反之，从点到点M的任一条路径与必有交点。记第一个交点为P，取关于直线的对称路径，以代替，得到从点O到点M的一条路径，即与是一一对应的。于是
从的几何意义我们可以得到
将，代入可以得到
由此得到了满足该数学结构的非负整数序列的个数。
致谢
本项研究工作得到了上海市科学技术委员会的资助，资助课题编号为13dz2260400；同时受到中国国家自然科学基金项目资助(项目批准号：11171114)，在此表示感谢。
参考文献