【中译】卡特兰数

BYR_KKK · 2024-11-17 23:59:24 · 个人记录

作者：来自贝尔格莱德大学的 Tanja Stojadinovic。

进度：20\%，目前进行到第二章（二叉树和数论内容）的生成函数推导二叉树数量部分。

前言

本篇论文介绍了数学上最著名的数列之一——卡特兰数。它在组合数学上广泛的应用和与其它著名数列的关系使得卡特兰数非常适合传授给任何阶段的数学家。

第一章 介绍

我们先来介绍卡特兰数在历史上那些令人激动的研究成果。感兴趣的读者可以前往文章【5】。最近的一项来自 Luo Jianjin 在 1988 年的研究表明，卡特兰数理论第一次出现是在中国数学家 Ming Antu 在 1731 年的著作。Leonard Euler 在 1751 年写给 Chirstian Goldbach 的信中将卡特兰数定义为 (n+2) 边形的三角划分数，并且发现了卡特兰数的生成函数。而在 Euler 与 Johann Segner 的通信中，后者发现了卡特兰数的递推公式。1838 年，Eugene Catalan 研究了卡特兰数与有 n 个括号组成的括号序列数目的关系。Arthur Cayley 在 1859 年利用卡特兰数的生成函数（generating function）对平面上的二叉树（the plane trees）计数。尽管这种数列无处不在，但是卡特兰数的命名并不遥远，并且该名称普遍应用开始于上世纪 70 年代早期。现代组合数学研究的领军人物 Richard Stanley，在他的著作 Enumerative Combinatorics 中列举了超过 200 种卡特兰数的组合意义。这项研究在最近发表于一本单行本专著【7】。在 2008 年的采访中，他将卡特兰数称作他最喜欢的数列（"favorite number sequence"）。另一本广为人知的相关专著为 【3】。

卡特兰数被如下定义：

该数列的前几项为：（从 C_0 开始）

卡特兰数在 OEIS 上的编号是 A000108。

在本论文中，我们将展现卡特兰数的主要组合意义。这种选择主要来自于作者的偏爱，这篇论文主要是作为对于卡特兰数进一步研究的出发点。在第二章中我们将对二叉树进行计数并且引出卡特兰数在数论上的主要内容，同时展示了卡特兰数和斐波那契数列（Fibonacci sequence）、切比雪夫多项式（Chebyshev polynomials）的联系。第三章将对二元群进行计数并且介绍二叉树集合上的 Tamari order（译者注：在群论上一般被理解为关联律的传递闭包）。还会引入一种特殊的凸多面体 associahedron，它的顶点数是卡特兰数。第四章将包含更多的组合意义，例如凸多边形的三角划分数、在多边形的斜对角线上随机游走、一些排列问题（排列一些点使得避免出现某些图案的方案数）、投票问题。

第二章 二叉树和数论内容

在图论中，树被定义成一种无环的简单图。只存在连向父亲节点的边的节点被称作叶子（原文："The nodes of a tree which are incident to a unique edge are called leaves"，译者采用了中文网上更加普遍的定义），其余被称为内部节点。有根树中存在一个节点为根。每一个有根树都在顶点集合上给出了一些关系，例如 u\ge v 代表 u 是 v 的父亲。一棵树被称作满二叉树当且仅当每个内部节点（包括根）都有恰好两个子节点。一颗二叉树总是一种被嵌入平面的平面树，因此一个内部节点的儿子被标定左、右的顺序。令 \tau 代表所有的有根满二叉树，相应地将 \tau_n 记作所有有 n 个节点的有根满二叉树。出于方便，下文我们称 T\in\tau 为一棵二叉树。在 \tau 中存在一种二元运算 *，* 对于任意 T_1,T_2\in\tau 都成立。* 得到的同样是一颗二叉树 T_3，T_3 通过新建一个根并分别将 T_1,T_2 作为左右儿子后得到的二叉树。* 运算没有交换律，因为上文所述内部节点的儿子被标定了顺序。根据 * 运算，\tau 集合可以被如下定义：

定义其生成函数：

从 n\ge 1 开始，每一棵二叉树 T\in\tau_n 都有形式 T=*(T_1,T_2)。