连分式在组合数中的相关性质

Exploration of Continued Fractions in the Application of Combinatorial Numbers

摘要

通过Flajolet的连分式组合学理论，研究一般组合数母函数的连分式展开式，一种自然的想法是考察与Motzkin数有代数联系的其他组合数，基于Motzkin和Catalan格路的研究以及对Schröder 数和Delannoy数组合模型的研究，发现Catalan格路两种不同格路径的转化关系，进而引出对其他组合数建立适当格路转化的思路，通过利用平面上某些带标签的格路径的母函数与Stieltjes-Jacobi型连分式等价定理，得出大Schröder路、小Schröder路的连分式表达式以及Delannoy路的连分式在代数方面的一些相关结论。

Abstract

Using Flajolet’s theory of combinatorial species, the study of the continued fraction expansion of the generating function for general combinatorial numbers naturally leads to the examination of other combinatorial numbers that have algebraic connections with Motzkin numbers. Based on the study of Motzkin and Catalan lattice paths, as well as the combinatorial models for Schröder numbers and Delannoy numbers, a transformation relationship between two different types of Catalan lattice paths is discovered. This leads to the idea of establishing appropriate lattice path transformations for other combinatorial numbers. By utilizing the equivalence theorem between the generating functions of certain labeled lattice paths on a plane and the Stieltjes-Jacobi type continued fractions, the continued fraction expressions for large Schröder paths, little Schröder paths are derived, and some algebraic conclusions related to Delannoy paths are obtained.

Graphical abstract

关键词

连分式 / 格路径 / Motzkin路 / Schröder路

Key words

continued fraction / lattice path / Motzkin path / Schröder path

在组合数学领域，连分式作为一种强大的工具，已经被广泛应用于研究组合数序列的性质。Flajolet的工作^[1]在这方面具有开创性，不仅证明了Stieltjes-Jacobi型的普通连分式与Motzkin路径的普通型生成函数之间的等价关系，而且还提出了多种研究路径，为后续的研究者提供了丰富的思路。Zhu等^[2]利用Stieltjes-Rogers定理，成功证明广义欧拉多项式的一般生成函数具有Jacobi型连分式表达式。这项工作不仅扩展了连分式在组合数学中的应用范围，而且也为理解和计算更复杂的组合结构提供了新的视角。Lin等^[3]在二项欧拉多项式的研究中，也发现了其一般生成函数的Jacobi型连分式表达式。这一发现进一步证实了连分式在处理特定类型的多项式时的有效性。Guo等^[4]则利用正交多项式理论，证明了广义有序Bell多项式的一般生成函数同样具有Jacobi型连分式表达式。他们的工作不仅展示了正交多项式理论在组合数学中的应用，而且也为理解和计算有序Bell多项式提供了新的工具。Fu等^[5]利用Flajolet的连分式模型和格路的对称性证明了Berstel等人提出的开放问题。Deb等^[6]探讨了具有每周期-1权重的分式连分数，特别是对于具有大量独立统计量的通用生成函数，每个周期被赋予-1权重时，可以得到一个非常有意义的连分数。

本文通过Motzkin路径与代数组合数之间的双射关系，将两类典型组合结构的格路表征纳入Flajolet连分式框架的解析体系，实现了路径系统与连分式系数的同构对应。这种基于符号方法和复解析技术的转化范式，不仅为路径图系统的递推关系研究提供了新的分析工具，其揭示的生成函数与格路权重的内在关联性，更拓展了组合数学中树结构、排列模式等领域的交叉研究方法。

1 Motzkin路

1.1 Motzkin路定义及表示

定义1 格路径。在平面直角坐标系中，横坐标与纵坐标均为整数的点称为平面格点。平面格路径指的是，从起点到终点仅走平面格点的路，其中路径的长度是指其所走路的步数。这里只研究平面格路径，以下简称为格路径。

例1：图1是一条从(\mathrm{0,0})到(\mathrm{3,5})的格路径，它由3个水平步c=(\mathrm{1,0})和5个垂直步u=(\mathrm{0,1})组成。由此，上述给定的格路径可以由3个c和5个u的序列\left(c,u,u,c,u,u,c,u\right)唯一确定。

在计数组合学中，通过对格路径所走的步做不同的限制可以得到不同类型的格路径。格路计数是研究不同类型的格路的数目和性质。本文主要研究带标号的Motzkin路，下面来介绍Motzkin路。

定义2 Motzkin路。一条n阶的Motzkin路指的是在平面直角坐标系的第一象限中从坐标原点(\mathrm{0,0})出发到点(n,\mathrm{0})的格路径，其中允许的步法仅含上步a=(\mathrm{1,1})、下步b=(\mathrm{1},-\mathrm{1})和水平步c=(\mathrm{1,0})，且不允许走到x轴下方^[7-8]。

例2:一条n阶Motzkin路可以用一个含有n个字母的词u=\left(u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n\right)表示，u_i\in \left\{a,b,c\right\}，并且任意k长的子序列\left(u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_k\right)(k\le n)中，从左至右依次计数字母a的个数总是不小于字母b的个数。对于每一条Motzkin路可以分别对上步a、下步b和水平步c赋予权重来记录每一步起始位置的高度。图2是一条长度为9的带标签的Motzkin路。

令M_n表示所有n阶Motzkin路的个数，对于任意一条n阶Motzkin路\omega，由于起始步只有a或c两种，所以可以做如下两种讨论：1）若第1步为水平步c时，则此时相当于在\left(n-\mathrm{1}\right)阶Motzkin路的第1步前面加上一个水平步c，它的个数等于M_{n-\mathrm{1}}；2）若第1步为右上步a时，总可以找到第一次回到x轴的右下b步，也即Motzkin路\omega可以分解为a{\omega }_{\mathrm{1}}b{\omega }_{\mathrm{2}}的形式，其中{\omega }_{\mathrm{1}}和{\omega }_{\mathrm{2}}为两条Motzkin路，由此可以得出若第1步为a的n阶Motzkin路个数为{\displaystyle \sum _{k=\mathrm{0}}^{n-\mathrm{2}}}{M}_k{M}_{n-\mathrm{2}-k}，因此证明Motzkin数满足如下的递推关系式^[9]：

M_n=M_{n-\mathrm{1}}+{\displaystyle \sum _{k=\mathrm{0}}^{n-\mathrm{2}}}{M}_k{M}_{n-\mathrm{2}-k}（1）

式中：n\ge \mathrm{2}；前10项Motzkin数为1、1、2、4、9、21、51、127、323、835、2 188（参见文献[10]中的序列A001006）。

定义3 Dyck路。一条\mathrm{2}n阶的Dyck路指从坐标原点\left(\mathrm{0,0}\right)出发到点\left(\mathrm{2}n,\mathrm{0}\right)的格路径，允许的步法仅含上步a=(\mathrm{1,1})和下步b=(\mathrm{1},-\mathrm{1})，且不允许走到x轴下方的格路径。\mathrm{2}n阶的Dyck路的个数为第n个Catalan数^[6-7]，有：

C_n=\frac{\mathrm{1}}{n+\mathrm{1}}\left(\begin{array}{c}\mathrm{2}n\\ n\end{array}\right)

其中：n\ge \mathrm{0}；前10项Catalan数为1、1、2、5、14、42、132、429、1 430、4 862（见文献[10]中序列A000108）。

定义4 大Schröder路。半长为n的Schröder路是从坐标原点(\mathrm{0,0})出发到点(n,n)的格路径，其中允许的步法仅含垂直步u=(\mathrm{0,1})、水平步c=(\mathrm{1,0})和上步a=(\mathrm{1,1})，且不允许走到直线y=x下方的格路径。

定义5 小Schröder路是指在大Schröder中不含上步a=(\mathrm{1,1})的路^[11]。

半长为n的Schröder路的个数是大Schröder数，记作r_n, 大Schröder数的母函数r(t)满足：

r(t)=\frac{\mathrm{1}-t-\sqrt[]{\mathrm{1}-\mathrm{6}t+t^{\mathrm{2}}}}{\mathrm{2}t}

半长为n的小Schröder路的个数是小Schröder数，记作s_n,小Schröder数的母函数s(t)满足：

s(t)=\frac{\mathrm{1}+t-\sqrt[]{\mathrm{1}-\mathrm{6}t+t^{\mathrm{2}}}}{\mathrm{4}t}

其中，前10项大Schröder数和小 Schröder数分别为1、2、6、22、90、394、1 806、8 558、41 586、206 098和1、1、3、11、45、197、903、4 279、20 793、103 049（见文献[10]中的序列A006318和序列A001003）

定义6 Delannoy路。Delannoy路指从坐标原点(\mathrm{0,0})出发到点(n,k)的格路径，其中允许的步法仅含水平步c=(\mathrm{1,0})、垂直步u=(\mathrm{0,1})和上步a=(\mathrm{1,1})^[12-13]。

根据Delannoy路的步法描述，由(n,k)的前一步有3种可能的情况，很容易得到Delannoy序列的递归关系：d\left(n,k\right)=d\left(n,k-\mathrm{1}\right)+d\left(n-\mathrm{1},k-\mathrm{1}\right)+d\left(n-\mathrm{1},k\right)，同时，它有如下的母函数^[14]：

{\displaystyle \sum _{n,k=\mathrm{0}}^{\mathrm{\infty }}}D(n,k)x^n{y}^k=\frac{\mathrm{1}}{\mathrm{1}-x-y-xy}

特别的，当n=k时，D_n=d\left(n,n\right)称为第n个中心Delannoy数，其母函数为

{\displaystyle \sum _{n=\mathrm{0}}^{\mathrm{\infty }}}{D}_n{t}^n=\frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-\mathrm{6}t+t^{\mathrm{2}}}}（2）

式中，前10项Delannoy数为1、3、13、63、321、1 683、8 989、48 639、265 729（见文献[10]中的序列A001850）。

1.2 形式幂级数的相关介绍

定义7 形式幂级数。在域k上，对于所有系数s_n\in k，序列{\left(s_n\right)}_{n\in \mathbb{N}}的一个母函数是关于变量x的形式幂级数\sum _{n\in \mathbb{N}}{s}_n{x}^n。对于所有的s_n\in k形式幂级数构成一个交换环，记为k⟦x⟧^[15]。

例3：Motzkin数的母函数为

\begin{array}{l}\sum _{n\ge \mathrm{0}}{M}_n{x}^n=\frac{\mathrm{1}-x-\sqrt[]{\mathrm{1}-\mathrm{2}x-\mathrm{3}{x}^{\mathrm{2}}}}{\mathrm{2}{x}^{\mathrm{2}}}=\\ \frac{\mathrm{2}}{\mathrm{1}-x+\sqrt[]{\mathrm{1}-\mathrm{2}x-\mathrm{3}{x}^{\mathrm{2}}}}=\\ \mathrm{1}+x+\mathrm{2}x{}_{}{}^{\mathrm{2}}+\mathrm{4}{x}^{\mathrm{3}}+\mathrm{9}{x}^{\mathrm{4}}+\mathrm{21}{x}^{\mathrm{5}}+\cdots \end{array}（3）

且母函数满足：

M\left(x\right)=\mathrm{1}+xM\left(x\right)+x^{\mathrm{2}}M{\left(x\right)}^{\mathrm{2}}（4）

证明：考虑M\left(x\right)=\mathrm{1}+xM\left(x\right)+x^{\mathrm{2}}M{\left(x\right)}^{\mathrm{2}}两边x^n的系数。在等式两边x^{\mathrm{0}}的系数是1。下面考虑当n>\mathrm{0}的情况，由于根据母函数的定义，从而得出\left[x^n\right]M\left(x\right)=M_n。在\mathrm{1}+x^{\mathrm{2}}M{\left(x\right)}^{\mathrm{2}}中x^n的系数等于在M{\left(x\right)}^{\mathrm{2}}中的x^{n-\mathrm{2}}系数，即：{\displaystyle \sum _{k=\mathrm{0}}^{n-\mathrm{2}}}{M}_k{M}_{n-\mathrm{2}-k}。

且在xM(x)中x^n的系数等于M(x)中x^{n-\mathrm{1}}的系数，即：M_{n-\mathrm{1}}。

综上，得出M_n=M_{n-\mathrm{1}}+{\displaystyle \sum _{k=\mathrm{0}}^{n-\mathrm{2}}}{M}_k{M}_{n-\mathrm{2}-k}。

由式（1）的成立，从而给出了式（4）的证明。通过式（4）可以得到式（3）成立。

1.3 连分式的相关介绍

定义8 （连分式）连分式是满足如下条件的一个有序对序列\left(\left\{a_n\right\},\left\{b_n\right\},\left\{f_n\right\}\right)^[16]：1）{\left\{a_n\right\}}_{\mathrm{0}}^{\mathrm{\infty }}和{\left\{b_n\right\}}_{\mathrm{0}}^{\mathrm{\infty }}是两个给定的序列，且a_n\ne \mathrm{0}; 2）\left\{f_n\right\}是通过下式定义的一个扩充序列：

f_n=S_{\mathrm{0}},n=\mathrm{0,1},\mathrm{2},\cdots

式中：

\left\{\begin{array}{c}\begin{array}{l}{S}_{\mathrm{0}}\left(\alpha \right)=s_{\mathrm{0}}\left(\alpha \right),\\ S_n\left(\alpha \right)=S_{n-\mathrm{1}}\left(s_n\left(\alpha \right)\right),\end{array}\\ \begin{array}{l}{s}_{\mathrm{0}}\left(\alpha \right)=b_{\mathrm{0}}+\alpha ,\\ s_n\left(\alpha \right)=\frac{a_n}{b_n+\alpha },\end{array}\end{array}n=\mathrm{0,1},\mathrm{2},\cdots \right.

将其展开即为

b_{\mathrm{0}}+\frac{a_{\mathrm{1}}}{b_{\mathrm{1}}+\frac{a_{\mathrm{2}}}{b_{\mathrm{2}}+\frac{a_{\mathrm{3}}}{b_{\mathrm{3}}+\ddots }}}。

a_n和b_n分别为连分式（上式）的第n次部分分子和部分分母，\frac{a_n}{b_n}为连分式的第n节，f_n为连分式（上式）的第n次逼近。

定义9 定义如下形式为Jacobi型连分式，简称J-连分式：

J\left(z\right)=\frac{\mathrm{1}}{\mathrm{1}-c_{\mathrm{0}}z-\frac{a_{\mathrm{0}}{b}_{\mathrm{1}}{z}^{\mathrm{2}}}{\mathrm{1}-c_{\mathrm{1}}z-\frac{a_{\mathrm{1}}{b}_{\mathrm{2}}{z}^{\mathrm{2}}}{\ddots }}}。

每一个J-连分式都关于变元z有一个对应的形式幂级数表达式：

J\left(z\right)=\sum _{n\ge \mathrm{0}}{R}_n{z}^n。

式中，R_n为Jacobi-Rogers多项式，由Rogers首次发现。

定理1 令E^{[h]}，h\ge \mathrm{0}，有以下形式^[17-18]：

E^{[h]}=\frac{\mathrm{1}}{\mathrm{1}-c_{\mathrm{0}}-\frac{a_{\mathrm{0}}|b_{\mathrm{1}}}{\mathrm{1}-c_{\mathrm{1}}-\frac{a_{\mathrm{1}}|b_{\mathrm{2}}}{\begin{array}{l}\ddots \\ \mathrm{1}-c_{h-\mathrm{1}}-\frac{a_{h-\mathrm{1}}|b_h}{\mathrm{1}-c_h}\end{array}}}}。

式中，\left(u|v\right)/w表示u{w}^{-\mathrm{1}}v（‘|’表示u、v、w是不对称的），有：

1）序列E_{h\ge \mathrm{0}}^{[h]}收敛，且极限定义为下述连分式的形式：

\underset{h\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{E}^{[h]}=\frac{\mathrm{1}}{\mathrm{1}-c_{\mathrm{0}}-\frac{a_{\mathrm{0}}|b_{\mathrm{1}}}{\mathrm{1}-c_{\mathrm{1}}-\frac{a_{\mathrm{1}}|b_{\mathrm{2}}}{\mathrm{1}-c_{\mathrm{2}}-\frac{a_{\mathrm{2}}|b_{\mathrm{3}}}{\ddots }}}}。

2）Motzkin路径集P的特征级数与序列E_{h\ge \mathrm{0}}^{[h]}极限相等：

E\left(P\right)=\frac{\mathrm{1}}{\mathrm{1}-c_{\mathrm{0}}-\frac{a_{\mathrm{0}}|b_{\mathrm{1}}}{\mathrm{1}-c_{\mathrm{1}}-\frac{a_{\mathrm{1}}|b_{\mathrm{2}}}{\mathrm{1}-c_{\mathrm{2}}-\frac{a_{\mathrm{2}}|b_{\mathrm{3}}}{\ddots }}}}。

以上定理是组合学中连分式的核心。由此可以将Motzkin路的形式幂级数展开成连分式的形式。通过态射和赋值，可以将Motzkin路统计量普通型母函数转化为对应连分式的形式。

2 连分式在Motzkin数中的应用

通过上一节的分析，建立了组合统计量的普通型母函数与对应连分式的关系，下面给出Motzkin数和Catalan数的连分式形式。

2.1 Motzkin 数及连分式表达式

例4：1）Motzkin数M_n表示长为n的Motzkin路数量，其母函数的连分式展开为^[16]

\sum _{n\ge \mathrm{0}}{M}_n{z}^n=\frac{\mathrm{1}}{\mathrm{1}-z-\frac{z^{\mathrm{2}}}{\mathrm{1}-z-\frac{z^{\mathrm{2}}}{\ddots }}}。

2）Catalan数C_n表示不含水平步的长为\mathrm{2}n的路径个数，母函数的连分式展开为

\sum _{n\ge \mathrm{0}}{C}_n{z}^n=\frac{\mathrm{1}}{\mathrm{1}-\mathrm{1}\cdot z-\frac{\mathrm{1}\cdot z^{\mathrm{2}}}{\mathrm{1}-\mathrm{2}\cdot z-\frac{\mathrm{1}\cdot z^{\mathrm{2}}}{\ddots }}}。

证明：对于1）定义如下态射{\mu }_{\mathrm{1}}：对任意的j\ge \mathrm{0},令{\mu }_{\mathrm{1}}\left(a_j\right)={\mu }_{\mathrm{1}}\left(c_j\right)=z，同时对于任意的k\ge \mathrm{1}，令{\mu }_{\mathrm{1}}\left(b_k\right)=z，利用定理1，即可得到Motzkin数的母函数的连分式展开式。

对于2）而言定义如下态射{\mu }_{\mathrm{2}}：对任意的j\ge \mathrm{0},令{\mu }_{\mathrm{2}}\left(a_j\right)=z,{\mu }_{\mathrm{2}}\left(c_j\right)=jz，且对于任意的k\ge \mathrm{1}，令{\mu }_{\mathrm{2}}\left(b_k\right)=z，同时利用定理1，即可得到Catalan数的母函数的连分式展开式。

关于Motzkin数和Catalan数可以得出两者的母函数分别有如下形式：

\sum _{n\ge \mathrm{0}}{M}_n{z}^n=\frac{\mathrm{1}-z-\sqrt[]{\mathrm{1}-\mathrm{2}z-\mathrm{3}{z}^{\mathrm{2}}}}{\mathrm{2}z}

和

\sum _{n\ge \mathrm{0}}{C}_n{z}^n=\frac{\mathrm{1}-\sqrt[]{\mathrm{1}-\mathrm{4}z}}{\mathrm{2}z}

同时Motzkin数与Catalan数有如下的关系：

M_n={\displaystyle \sum _{k=\mathrm{0}}^{⌊n/\mathrm{2}⌋}}\left(\begin{array}{c}n\\ \mathrm{2}k\end{array}\right)C_k。

3 主要结果

通过构造不同的代数态射对Motzkin数的生成函数进行变换，可以系统化地推导其母函数的多重连分式展开形式。本研究以例4中Motzkin数的态射结构为基点，通过调整态射组合规则（如路径步长的约束条件、峰值位置限制等），揭示了受限Motzkin路径与大小Schröder数之间的深层关联。

3.1 限制的Motzkin数及连分式表达式

性质1：设M_{i,j}表示从(\mathrm{0,0})到(i,j)且上边界为h的部分Motzkin路的个数，则M_j\left(z\right)为序列{\left(M_{i,j}\right)}_{i,j\ge \mathrm{0}}的母函数如下式：M_j\left(z\right)={\displaystyle \sum _{i=j}^{\mathrm{\infty }}}{M}_{i,j}{z}^i，\mathrm{0}\le j\le h-\mathrm{1}，有M_{\mathrm{0}}(z)的连分式展开式为

M_{\mathrm{0}}(z)=\frac{\mathrm{1}}{\mathrm{1}-z-\frac{z^{\mathrm{2}}}{\mathrm{1}-z-\frac{\ddots }{\mathrm{1}-z-\frac{z^{\mathrm{2}}}{\mathrm{1}-z-\frac{z^{\mathrm{2}}}{\mathrm{1}-z}}}}}。

证明：定义态射{\mu }_{\mathrm{3}}：对任意的h-\mathrm{1}\ge j\ge \mathrm{0}，令{\mu }_{\mathrm{3}}\left(a_j\right)={\mu }_{\mathrm{3}}\left(c_j\right)=z，任意的h\ge k\ge \mathrm{1}，令\mu \left(b_k\right)=z，利用定理1，即可得到上边界为h的部分Motzkin数的母函数连分式展开式。

性质2：设M_{n,k}表示所有n阶Motzkin路中包含了k个水平步的格路径的个数，则对于它的母函数\sum _{n,k\ge \mathrm{0}}{M}_{n,k}{u}^k{x}^n，有：

\sum _{n,k\ge \mathrm{0}}{M}_{n,k}{u}^k{z}^n=\frac{\mathrm{1}}{\mathrm{1}-zu-\frac{z^{\mathrm{2}}}{\mathrm{1}-zu-\frac{z^{\mathrm{2}}}{\ddots }}}。

证明：只需要对例4的1）中的态射添加对水平步的数量标记，因此引入一个新的变量。定义态射\mu：对任意的j\ge \mathrm{0},k\ge \mathrm{1}，令\mu \left(a_j\right)=\mu \left(b_k\right)=z且令\mu \left(c_j\right)=zu。

利用M_{n,k}的递推关系可以得到上述母函数的闭公式：

\sum _{n,k\ge \mathrm{0}}{M}_{n,k}{u}^k{z}^n=\frac{\mathrm{1}+(\mathrm{2}-u)z-\sqrt[]{{(\mathrm{1}-uz)}^{\mathrm{2}}-\mathrm{4}{z}^{\mathrm{2}}}}{\mathrm{2}z}。

3.2 Schröder数的性质及连分式表示

Flajolet的模型中，使用的格路径的基础步仅允许上步a=(\mathrm{1,1})、下步b=(\mathrm{1},-\mathrm{1})和水平步c=(\mathrm{1,0})，同时格路径不允许走到x轴的下方。对于Catalan数，Stanley列举了66种不同的组合模型进行解释。

例如，Catalan数表示对所有n阶Catalan路径的个数，这里的Catalan路径在平面中从坐标原点(\mathrm{0,0})出发到点(n,\mathrm{0}) 的格路径，其中允许的步法仅含水平步c=(\mathrm{1,0})、垂直步u=(\mathrm{0,1})和上步a=(\mathrm{1,1})且不允许走到y=x的下方。这种步法与定义3的步法可以建立一个一一映射，从而将上述模型转换为符合Flajolet构建的连分式展开模型^[7-8]。

对于许多组合统计量的格路模型，并不满足这种基础步法，由此考虑从与Motzkin数和Catalan数相关联的其他组合数出发构建适当的变换，或建立合适的等价模型^[19-20]。

引理1：构建定义5中半长为n的小Schröder路，从(\mathrm{0,0})到(\mathrm{2}n,\mathrm{0})始终保持在x轴上方且允许的步集为上步a=\left(\mathrm{1,1}\right)和下步b=\left(\mathrm{1},-\mathrm{1}\right)一一映射。

证明：从(\mathrm{0,0})到(\mathrm{2}n,\mathrm{0})的小Schröder路可以通过一个限制的Motzkin格路来计数，取连续步(\mathrm{1},i_{\mathrm{1}}),(\mathrm{1},i_{\mathrm{2}}),\dots ,(\mathrm{1},i_{\mathrm{2}n})，这与例2中的长为\mathrm{2}n的词u=\left(u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{\mathrm{2}n}\right)形成了一一映射，其中u_i\in \left\{a,b\right\}，并且任意k长的子序列\left(u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_k\right)(k\le \mathrm{2}n)中，从左至右依次计数字母a的个数总是不小于字母b的个数；这个词u对应于从(\mathrm{0,0})到(n,n)的路径，如果i_j=\mathrm{1}，则第j步是(\mathrm{1,0})，并且如果i_j=-\mathrm{1}，则第j步是(-\mathrm{1,0})。

由此，可以利用Flajolet构建的几何模型写出小Schröder数的连分式表达式：

性质3：小Schröder数s_n表示半长为n从坐标原点(\mathrm{0,0})出发到点(n,n)的格路径，其中允许的步法仅含垂直步u=(\mathrm{0,1})，水平步c=(\mathrm{1,0})，且不允许走到直线y=x下方的格路径个数，母函数的连分式展开为

\sum _{n\ge \mathrm{0}}{s}_n{z}^n=\frac{\mathrm{1}}{\mathrm{1}-\frac{z}{\mathrm{1}-\frac{z}{\mathrm{1}-\frac{z}{\ddots }}}}。

证明：定义如下态射\mu：对任意j\ge \mathrm{0},令\mu \left(a_j\right)=z,\mu \left(c_j\right)=\mathrm{0}且任意k\ge \mathrm{1}，令\mu \left(b_k\right)=\mathrm{1}，结合定理1，可得小Schröder数母函数的连分式展开式。

推论1：对于大Schröder数，它与 Catalan数有如下联系。对于一个n阶恰含有k个水平步c的Schröder路，当且仅当它恰含有\left(n+k\right)步，这里有\left(\begin{array}{c}n+k\\ n-k\end{array}\right)种方式选择\left(n-k\right)个上步a，同时移除所有的上步可以得到一个k阶的Catalan路，由此得到\left(\begin{array}{c}n+k\\ k\end{array}\right)C_k恰好等于所有n阶恰含有k个水平步c的Schröder路的个数，即：r_n={\displaystyle \sum _{k=\mathrm{0}}^n}\left(\begin{array}{c}n+k\\ k\end{array}\right)C_k,n\ge \mathrm{0}。

采用与小Schröder数同样的方式，可以得到大Schröder数的连分式展开式，即：

\sum _{n\ge \mathrm{0}}{r}_n=\frac{\mathrm{1}}{\mathrm{1}-x-\frac{x}{\mathrm{1}-x-\frac{x}{\mathrm{1}-x-\frac{x}{\ddots }}}}。

3.3 中心Delannoy数的有关性质

命题1：中心Delannoy序列{\displaystyle \sum _{n=\mathrm{0}}^{\mathrm{\infty }}}{D}_n{t}^n是下面双变元有理级数的对角元:

R(x,y)={\displaystyle \sum _{n,k=\mathrm{0}}^{\mathrm{\infty }}}D(n,k)x^n{y}^k=\frac{\mathrm{1}}{\mathrm{1}-x-y-xy}。

证明：首先，始终有\frac{\mathrm{1}}{\mathrm{1}-x-y-xy}=\sum _{i\ge \mathrm{0}}{(x+y+xy)}^{\mathrm{2}i}成立。有：

\begin{array}{l}R(x,y)=\frac{\mathrm{1}}{\mathrm{1}-x-xy-xy}=\\ \sum _{i\ge \mathrm{0}}{(x+y+xy)}^i=\\ \sum _{i\ge \mathrm{0}}\sum _{j\ge \mathrm{0}}\left(\begin{array}{c}i\\ j\end{array}\right){(x+y)}^j{\left(xy\right)}^{i-j}=\\ \sum _{i\ge \mathrm{0}}\sum _{j\ge \mathrm{0}}\left(\begin{array}{c}i\\ j\end{array}\right)\sum _{k\ge \mathrm{0}}\left(\begin{array}{c}j\\ k\end{array}\right)x^k{y}^{j-k}{\left(xy\right)}^{i-j}:=\\ \sum _{m,n\ge \mathrm{0}}{a}_{m,n}{x}^m{y}^n\mathrm{。}\end{array}

现在需计算R\left(x,y\right)的对角元，即形式幂级数\left(DR\right)\left(x\right)=\sum _{n\ge \mathrm{0}}{a}_{n,n}{x}^n，在表达式\sum _{i\ge \mathrm{0}}\sum _{j\ge \mathrm{0}}\left(\begin{array}{c}i\\ j\end{array}\right)\sum _{k\ge \mathrm{0}}\left(\begin{array}{c}j\\ k\end{array}\right)x^k{y}^{j-k}

{\left(xy\right)}^{i-j}中，唯一能使x和y指数相等的j、k，应满足k=j-k，因此j为偶数即j=\mathrm{2}k，随后由\left(DR\right)\left(x\right)=

\sum _{i\ge \mathrm{0}}\sum _{k\ge \mathrm{0}}\left(\begin{array}{c}i\\ \mathrm{2}k\end{array}\right)\left(\begin{array}{c}\mathrm{2}k\\ k\end{array}\right)x^{i-k}可知，上式与式（1）相等。

基于格路径与Prouhet Thue Morse序列的研究^[5]，一个自然的问题就是是否可以通过连分式组合理论证明该命题。

4 结束语

介绍了Flajolet在连分式组合学理论中的研究，基于文中提出的研究思路，对大Schröder 路、小Schröder 路的连分式表达式从格路的角度做了简单地探索；最后给出了中心Delannoy序列是双变元有理级数的对角元的一个代数证明，同时留下了关于命题1是否存在组合证明的思考。

通过这些研究，可以看到连分式在组合数学中的重要性和应用潜力。随着更多研究者的关注和努力，连分式无疑将在未来的组合数学研究中发挥更大的作用。

参考文献

[1] FLAJOLET P. Combinatorial aspects of continued fractions［J］. Discrete Mathematics， 1980，32（2）：125-161.

[2] ZHU B X. A generalized Eulerian triangle from staircase tableaux and tree-like tableaux［J］. Journal of Combinatorial Theory， Series A， 2020，172：No.105206.

[3] LIN Z C， WANG D G L， ZENG J. Around the q-binomial-Eulerian polynomials［J］. European Journal of Combinatorics， 2019，78：105-120.

[4] GUO W M， ZHU B X. A generalized ordered Bell polynomial［J］. Linear Algebra and Its Applications， 2020，588：458-470.

[5] FU S S， GAO B. Lattice paths and the prouhet-thue-morse sequence［J］. Theoretical Computer Science， 2024，1022：No.114885.

[6] DEB B， SOKAL A D. A remark on continued fractions for permutations and D-permutations with a weight -1 per cycle［DB/OL］. （2023-06-20）［2024-12-18］.

[7] BERNHART F R. Catalan， motzkin， and riordan numbers［J］. Discrete Mathematics， 1999，204（1-3）：73-112.

[8] 丁云.Dyck路，Motzkin路和Schr o ¨ der路上峰的计数［D］.上海：华东师范大学，2011：1-49.

[9] OSTE R， VAN DER JEUGT J. Motzkin paths， motzkin polynomials and recurrence relations［J］. The Electronic Journal of Combinatorics， 2015，22（2）：No.2.8.

[10] FINCH S. The on-line encyclopedia of integer sequences［J］. The Mathematical Intelligencer， 2021，43（2）：146-147.

[11] QI F， SHI X T， GUO B N. Some properties of the schröder numbers［J］. Indian Journal of Pure and Applied Mathematics， 2016，47（4）：717-732.

[12] CLAPPERTON J A， LARCOMBE P J. The Delannoy numbers： three new Non-linear identities［J］. Bulletin of the Institute of Combinatorics and its Applications，2012（64）：39-56.

[13] BANDERIER C， SCHWER S. Why Delannoy numbers？［J］. Journal of Statistical Planning and Inference， 2005，135（1）：40-54.

[14] QI F， ČERŇANOVÁ V， SHI X T， et al. Some properties of central Delannoy numbers［J］. Journal of Computational and Applied Mathematics， 2018，328：101-115.

[15] BERSTEL J， AARON L， CHRISTOPHE R， et al. Combinatorics on words： christoffel words and repetitions in words［M］. Providence， USA： American Mathematical Society， 2009：96-98.

[16] ALLOUCHE J P， SHALLIT J. Automatic sequences［M］. Cambridge， UK： Cambridge University Press， 2003：1-588.

[17] ERICKSEN L. Lattice path combinatorics for multiple product identities［J］. Journal of Statistical Planning and Inference， 2010，140（8）：2213-2226.

[18] MANSOUR T， SCHORK M， SUN Y D. Motzkin numbers of higher rank： generating function and explicit expression［J］. Journal of Integer Sequences， 2007，10（7）：No.07.7.4.

[19] YANG L， YANG S L. A relation between Schröder paths and motzkin paths［J］. Graphs and Combinatorics， 2020，36（5）：1489-1502.

[20] RICHARD S. Enumerative combinatorics， volume 2 ［M］. Cambridge， USA： Cambridge University Press， 1999：168-178.