本文档为Frank R. Bernhart于1999年在《Discrete Mathematics》期刊上发表的题为“Catalan, Motzkin, and Riordan numbers”的学术论文。该论文并非对某一项单一原创性研究的报告，而是一篇综合性、综述性与原创性并存的学术论文，旨在对Catalan、Motzkin以及Riordan这三类重要的整数序列进行统一的、深入的梳理、阐释与关联。论文的核心在于通过组合结构、递归关系、生成函数、差分三角形（difference triangles）和拉格朗日反演（Lagrange inversion）等多种数学工具，系统性地揭示这些序列之间的内在联系、组合意义及其在特定数学问题（如图的着色多项式）中的应用，最终论证Riordan数（或称“环数”）与Motzkin数同等基础与重要。因此，本文档属于类型b：一篇综述性与研究性结合的论文。

作者、发表信息及主题

本文的作者是Frank R. Bernhart，所属机构为美国纽约州罗切斯特的“140 Whiteford Road”。论文发表于1999年，收录于《Discrete Mathematics》第204卷（73-112页），并特别致敬了H.W. Gould七十岁生日。论文的主题是探讨三个在组合数学（Discrete Mathematics）中频繁出现且密切相关的整数序列：Catalan数（C_n）、Motzkin数（M_n）以及一个在当时尚未被广泛命名、作者提议称为Riordan数或环数（R_n）的序列。论文的重点在于提供一个统一的视角，展示它们的组合结构、相互转换关系以及Riordan数在图论中的特定应用。

主要观点及其论据

观点一：三类序列（Catalan, Motzkin, Riordan）具有深刻而直观的组合对应关系，可以通过一系列组合结构（族）来定义和阐释。

作者的核心贡献之一在于将抽象的序列具象化为具体的组合对象族。对于每个序列，论文都给出了多个等价的组合计数问题实例，并强调了它们之间直接的、可视化的“一一对应”（bijective correspondences），而非仅仅依赖代数推导。

• Catala数的组合族：包括：

  1. 三角剖分（Deltoids）：将凸(n+2)边形用互不相交的对角线划分为三角形的方法数。
  2. 平面配对（Planar pairs / Noncrossing pairs）：将圆周上2n个点两两配对并用n条互不相交的弦连接的方法数。这本质上是由双元素块构成的非交叉划分（noncrossing partitions）。
  3. 非交叉划分（Noncrossing partitions）：将圆周上n个点划分为互不相交且其代表边（弦）互不交叉的块（类）的方法数。 作者详细阐述了这些族之间的对偶关系。例如，三角剖分与“有根的立体平面树”（planted cubic trees）对偶；平面配对可以通过引入新点、进行棋盘着色，与非交叉划分建立对偶。这些具体的构造使得Catala数的标准递归关系 (C_{n+1} = C_0C_n + C1C{n-1} + … + C_nC_0) 变得直观，它对应于从这些组合对象中移除一条“基边”或关注第一个顶点所引出的分解。

• Motzkin数的组合族：包括：

  1. 非交叉部分配对（Noncrossing partial pairs）：在n个点中，允许部分点被两两配对（形成互不相交的弧），其余点保持孤立的方法数。这可以表示为一个由‘+’（弧左端）、‘0’（孤立点）、‘-’（弧右端）组成的序列，称为Motzkin形状。
  2. 平面灌木（Plane bushes）：具有(n+1)条边的、根节点度数大于1（短灌木）或等于1（高灌木）的平面树，且除根节点外，其他顶点度数不为2。
  3. 严格可行的非交叉划分（Strict feasible noncrossing partitions）：一种特殊的、第一个顶点是单点（singleton）的非交叉划分。 作者通过几何变换（如拉伸弧线）和树结构分析，展示了这些族之间的等价性。特别关键的是，Motzkin数M_n可以通过Riordan数分解为“上类”和“下类”，满足关系 (M_n = Rn + R{n+1})。

• Riordan数的组合族：作者将此序列与“环”（Ring）的概念联系起来，并给出了三个关键组合解释：

  1. 高/矮灌木（Tall/short bushes）：对应Motzkin数中灌木的两种子类，直接体现了上述 (M_n = Rn + R{n+1}) 的关系。
  2. 循环间隔（可行）的非交叉划分（Cyclically spaced / feasible noncrossing partitions）：这是论文的核心发现。指那些在圆周表示中，相邻顶点永不属于同一划分块的非交叉划分。这种划分与W. T. Tutte定义的“平面着色方案”（planar coloring schemes）等价，是研究n-环（n-ring）上着色多项式线性独立性的自然几何基。
  3. 无非点的非交叉划分（Noncrossing partitions with no singletons）：所有块大小至少为2的非交叉划分。通过与可行非交叉划分的对偶性，可以建立两者的一一对应。 作者还推导了Riordan数的标准递归关系：(R_{n+1} + (-1)^n = R_0R_n + R1R{n-1} + … + R_nR_0)，并通过灌木的分解（引入“例外”灌木的概念）给予了组合证明。

观点二：差分三角形（Difference triangles）是连接这些序列并推导其相互转化公式的优雅桥梁。

作者提出了一种基于“可行性”概念的差分三角形构造方法，提供了一种比传统代数证明更简洁、更直观的推导路径。 * 从Catalan数到Riordan和Motzkin数：考虑圆周上n个点的非交叉划分。定义一个划分是“k-可行”的，如果其前k个顶点都是“见证点”（即不与紧随其后的顶点相连）。显然，0-可行划分就是所有非交叉划分（计数为C_n），而n-可行划分就是可行的非交叉划分（计数为R_n）。如果一个n点的划分是k-可行但不是(k+1)-可行的，可以通过合并第(k+1)个点与其后点，转化为一个(n-1)点的k-可行划分。这一事实意味着，如果将k-可行划分的计数序列（n = k, k+1, …）作为差分三角形的行，那么下一行（(k+1)-可行划分计数）就是上一行的差分序列。从C_n序列（0-可行）开始构建此三角形，第一条对角线（由每次差分偏移得到）就是R_n序列，第二条对角线就是M_n序列。由此直接导出了连接公式： * (R_n = \sum_i (-1)^{n-i} \binom{n}{i} C_i) * (M_n = \sumi (-1)^{n-i} \binom{n}{i} C{i+1}) 反向关系（用R或M表示C）也可通过此三角形得到。 * 从Motzkin数到Catalan数：类似地，以Mn为初始行构建差分三角形，其第一条对角线是“加气的”Catalan序列（C+：在Catalan数间插0），这自然地引出了Touchard公式：(C{n+1} = \sum_i \binom{n}{2i} 2^{n-2i} C_i)，该公式也通过允许部分配对中的孤立点带“环”得到组合解释。

观点三：生成函数、特征方程和拉格朗日反演（Lagrange inversion）提供了统一处理这些序列代数性质的强大工具。

论文系统性地给出了三类序列的生成函数及其满足的特征方程： * Catalan: (y = 1 + x y^2) * Motzkin: (y = 1 + x y + x^2 y^2) * Riordan: (y = \frac{1 + x y^2}{1 + x}) 通过解二次方程，可以得到根式表达。更重要的是，作者展示了如何应用拉格朗日反演定理从这些方程中直接提取序列的封闭形式或求和表达式。 * 例如，对于Motzkin方程，令(z = xy)，得到(z = x(1 + z + z^2))。应用拉格朗日反演得到 ((n+1)M_n) 是 ((1+t+t^2)^{n+1}) 展开式中 (t^n) 的系数，这连接到了三项式系数（trinomial coefficients）。 * 对于Riordan方程，类似处理得到 ((n+1)R_n) 是 ((\frac{1}{1-t} - t)^{n+1}) 展开式中 (t^n) 的系数。 作者还展示了如何通过叠加和移位Pascal三角形（二项式系数表）和三项式系数表，分别构造出含有Catalan数和Motzkin/Riordan数的计算三角形，这些三角形本身具有简单的递归规则，便于计算。

观点四：Riordan数在图论，特别是平面图的着色多项式（chromatic polynomials/chromials）理论中具有根本性的应用价值。

这是论文后半部分深入阐述的原创性背景和动机。作者回顾，他于1977年在研究平面地图和图的着色理论时重新发现了这些数（即Riordan数）。 * 问题背景：Birkhoff和Lewis在其关于着色多项式的开创性工作中，研究了三价平面地图及其n-环（ring of order n）。为了重构整个地图的着色多项式，他们引入了“受约束的着色多项式”（constrained chromatic polynomials），其数量等于可行划分的总数 (v_n)（所有划分，不要求非交叉）。 * 作者的关键发现：作者指出，对于平面地图，如果考虑其平面着色方案（由Tutte定义），这些方案等价于对偶图中一个非交叉且循环间隔（可行） 的划分。这些划分构成了n-环上所有着色多项式的一个自然几何基。因此，Riordan数 (R_n) 恰好给出了当n-环包含任意内部构型时，线性独立的着色多项式的数目。 * 联系与推广：作者进一步指出了与更广序列的类比：所有n点划分数是Bell数 (B_n)，所有可行划分数是 (v_n)，所有无单点划分数是 (w_n)。令人惊讶的是，有组合对应关系表明 (B_n = vn + v{n+1}) 以及 (v_n = w_n)。这类似于 (C_n, M_n, R_n) 之间的关系，但去掉了“非交叉”的限制。这凸显了Riordan数在受限（平面、非交叉）组合结构中的核心地位。

观点五：论文展示了大量具体的组合对应、变换和图表，旨在作为序列研究的技术入门和直观指南。

除了上述核心观点，论文还包含了丰富的细节，体现了其作为“入门指南”（primer）的意图： * 具体对应示例：如平面树与半立方树（semi-cubic trees）的转换，用于体现Motzkin分解；增加二部图（increasing bipartite graphs, IBG）与格路径（lattice paths）、投票序列（ballot sequences）的相互转化，展示了从Motzkin形状生成众多等价计数族的通用方法。 * 特殊结构的展示：如从三角剖分的“边缘序列”（margin sequence）出发，构造具有“菱形性质”（水平乘积等于垂直乘积加1）的“带状图案”（frieze），并关联到特定的三对角矩阵行列式。 * 强调直观性：作者多次强调其呈现方式力求“视觉上令人信服”，抑制繁琐的细节，旨在使读者能够直观地把握对应关系。

论文的意义与价值

本文的意义与价值体现在以下几个方面： 1. 系统化与统一：将Catalan、Motzkin和Riordan这三个分散但密切相关的序列置于一个统一的框架下进行讨论，清晰地揭示了它们在组合结构、递归关系和生成函数层面的内在统一性。 2. 正名与提升：明确提出了“Riordan数”这一命名（基于Riordan早期工作），并通过详尽的组合解释和图论应用，论证了其与Motzkin数同等的基础性和重要性，提升了该序列在组合数学界的认知度。 3. 方法论的展示：论文本身就是组合数学研究方法的优秀范例。它综合运用了组合构造（族）、递归分解、对偶原理、生成函数、差分技巧、拉格朗日反演等多种工具，展示了如何从不同角度攻击和理解同一个数学对象。 4. 连接理论与应用：成功地将看似纯组合的Riordan数与图论中经典的着色多项式问题联系起来，为后者提供了一个清晰的组合几何解释，解决了Birkhoff和Lewis工作中关于线性独立基的一个具体问题，体现了组合数学在解决应用数学问题中的力量。 5. 丰富的资源与启发：论文提供了大量的等价问题、对应关系和开放类比（如与Bell数的类比），为后续研究者和学生提供了宝贵的研究线索、练习素材和灵感来源。其强调直观和对应的风格，也使其成为学习组合数学的优异教材章节。

Bernhart的这篇论文是一篇内容深厚、结构清晰、兼具综述性与原创性的杰出作品。它不仅系统梳理和关联了几个经典组合序列，更重要的是通过引入深刻的组合对应和明确的图论应用，确立了Riordan数在组合数学谱系中的关键地位，并为相关领域的研究提供了有力的工具和视角。