动机
选取哪些位置放置上升步,所数的是具有给定终点高度的单词,但这并不能保证其中间高度保持非负。前缀约束会记住符号的先后顺序,因此不能仅靠要求总数相等来施加。
反射法用一个精确的双射修复了这一不匹配。第一次跌到零以下的路径,其初始段可以被翻转,从而把“失败”转化为另一个终点的计数。把这些失败的数目减去,便得到卡特兰(Catalan)数。随后,首次返回分解说明了为什么同一个数列还能计数有序二叉树、括号化方式和三角剖分。重点在于找出可逆的构造,而不是罗列一些小数值恰好吻合却互不相关的对象。
形式母函数仅作为系数恒等式使用,不假设解析收敛性。
定义
定义 2.8.1
(前缀高度与投票条件)
上升步 使高度增加一,下降步 使高度减少一。含有 个上升步和 个下降步的单词从零出发,终点高度为 。弱投票单词是指每个前缀(包括空前缀)之后的高度都非负的单词。严格投票单词是非空单词,并且每个非空前缀之后的高度都严格为正。
半长为 的 Dyck 单词是含有 个上升步和 个下降步的弱投票单词。空单词是半长为零的唯一 Dyck 单词。以 表示这类单词的个数。等价地,把 解释为左括号, 解释为右括号:没有任何前缀所关闭的括号多于所打开的括号,并且最终两者总数相等。
定义 2.8.2
(平面满二叉树及其大小)
平面满二叉树是一棵有根树,其中每个顶点要么是叶子,要么恰有两个有序的子顶点,分别称为左子顶点和右子顶点。这里它的大小指内部顶点的个数,而不是顶点总数。一个内部顶点的两棵子树是各自独立的有序选择,交换它们可能改变这棵树。
对于二项式系数的计数,当 或 时约定 ,其中 为非负整数。这使得没有下降步的边界情形得到明确处理。下面所有路径都是有限的步骤单词,而不是任意的几何曲线。
定理/命题
定理 2.8.3
(反射给出弱与严格投票公式)
对于整数 ,弱投票单词的个数为
特别地,对每个 有 。对于整数 ,严格投票单词的个数为
严格情形的陈述针对非空单词,它并没有给空 Dyck 单词赋予矛盾的地位。
定理 2.8.4
(首次返回给出卡特兰递推式与级数)
初值为 ,且对 ,
因此,普通形式级数 是满足 且常数项为一的唯一级数,并且
其中形式平方根的常数项为一。具有 个内部顶点的平面满二叉树,以及对 个固定有序因子的完全括号化方式,其个数均为 。
闭式中的因子 来自反射计数,它并不是要求把所有对象分成无名的、每组该大小的若干组。之后的每一种解释,都需要各自的双射,或一个初值相同且已被证明的递推式。
证明思路或证明
证明
(在首次到达高度 处反射)
具有给定总数的无限制单词共有 个。设 ,并设某个单词不满足非负性。找出它第一个终点高度为负一的前缀,并在该前缀内把 与 全部互换。该前缀的下降步比上升步多一个,所以变换后的完整单词含有 个上升步和 个下降步。
反过来,任何具有变换后总数的单词,终点高度为 。因此它有第一个终点高度为一的前缀。将该前缀内的各步互换。在所选的第一个正高度之前,所有高度都非正;反射之后,这些高度都非负,直到新前缀第一次到达负一为止。这两个操作互为逆运算,且所用的首次到达时刻恰如上述所确定。于是,不良单词与所有含 个下降步的单词之间存在双射,后者的个数为 。若 ,则没有不良单词,所述约定使该减项为零。
相减即得弱公式;经过初等的阶乘约分,便得到其比值形式。取总数相等时,得到卡特兰闭式,其中包括空单词。对于 的严格投票单词,第一步必须是上升步。删去它,并把其余的高度都下移一。原来非空前缀的严格正性,恰好就是这个后缀的弱非负性,该后缀含有 个上升步和 个下降步。应用弱公式,并利用 化简,即得严格比值。
证明透视
首次到达时刻使反射可逆
有三个选择使这个映射成为双射。第一,切点是第一个高度为 的前缀;翻转任意一个违规段,并不能说明如何还原原来的单词。第二,被翻转的前缀恰好比 多一个 ,所以像的总数为 与 ;这是步数唯一改变之处,也是减项为 的原因。
第三,逆映射要求每个具有新总数的单词都有第一次到达高度 的时刻。它之所以存在,是因为这样的单词终止于 (这里用到 ),而高度每步只变化一。在该时刻之前高度至多为 ,翻转后至少为 ,而翻转后的前缀终止于 :像第一次到达 正是在同一位置。两个首次到达时刻因此互相对应,每个变换后的单词恰好被计数一次,不会遗漏或重复任何失败的单词。 的情形从不进入反射,而由约定 处理。
证明
(首次返回分解及其编码)
对于递推式,非空 Dyck 单词以 开头。设它第一次返回高度零时的步为与之匹配的下降步。它具有唯一的形式 ,其中 和 是 Dyck 单词:将最初那对匹配括号内部的高度减去一,并把返回之后的后缀视为从零开始。若 的半长为 ,则后缀的半长为 。反过来,任何这样的一对单词都给出一个具有该首次返回的 Dyck 单词。把两个独立计数的乘积求和,便证明了递推式。
现在,形式系数的乘法给出 。常数项之后的每个系数,都由递推式根据前面的系数确定,这证明了唯一性。令 。代入得 且 。具有该常数项的平方根是唯一的:在每个正次数上,新的系数出现两次,再加上已被确定的表达式,而二在有理数域上可逆。这就证明了平方根的表达式。它的分子常数项为零,所以除以 得到的是形式幂级数。二次方程的另一个符号,其分子常数项非零,会引入负次幂,因此它不是另一个形式幂级数解。
平面满二叉树要么是单个叶子(大小为零),要么是一个内部根加上一对有序的左右子树。把叶子编码为空 Dyck 单词,把内部根编码为 ,其中 分别编码它的两棵子树。首次返回能唯一地重构根处的分裂,所以这是保持大小的双射。对于括号化,把每次乘法变成一个内部顶点,把它的左右运算对象变成有序子树;固定的因子顺序从左到右标记各叶子。这个可逆的语法树构造证明了第二种解释。
例题详解
例题 2.8.5
(两种独立的计算都给出十四)
对于半长为四,反射公式给出 。由 ,首次返回给出 。每一项固定了第一对匹配括号内部的半长。无限制的平衡单词共有七十个,所以大多数具有给定总数的单词都不满足前缀条件。
例题 2.8.6
(弱正性与严格正性所计数的是不同的事件)
含有七个上升步和四个下降步时,无限制单词共有 个。弱计数为 。严格计数为 。弱单词可以在继续之前先返回零,严格单词则不可以。它们的终点高度都是三,所以仅凭终点信息无法区分这两个条件。
下面的互动图把坏单词直到首次到达高度 的前缀翻转,并把枚举所得的弱投票、严格投票与坏单词个数同公式比较,其中包括 、 的情形。
例题 2.8.7
(四个因子上的五种有序二叉结构)
有三个内部顶点时,根的子树大小可以是 、 或 ,分别贡献两种、一种和两种选择。因此共有五棵平面满二叉树。在四个有序因子上,它们对应于 、、、 和 。
左右顺序是每个构造的一部分。即使在结合运算下对它们求值会得到相同的值,这些书写出来的括号化方式仍然互不相同。枚举所计数的是语法或树结构,而不是不同的数值结果。
例题 2.8.8
(一条指定的多边形边提供另一种根分裂)
在有 个按圆周排列的顶点的凸多边形中,指定一条边界边。在三角剖分中,与该边相邻的三角形有唯一的第三个顶点。它把多边形分成两个较小的多边形区域,这两个区域的三角剖分可以独立选取;凸性保证它们的对角线位于各自的区域之内。
对 ,以 表示这类三角剖分的个数,并对仅由一条边界边构成的空区域(而非真正的双边多边形)规定 。选取第三个顶点,得到的区域大小以 和 为指标,因此 。反过来,把它们的三角剖分与指定的三角形拼合,可以唯一地重构原来的三角剖分。由于初值相同,这就是卡特兰递推式;因此五边形有五种三角剖分。空区域的约定,正是用来处理第三个顶点与根边的某个端点相邻的情形。
计数并不能解决识别所需的记忆
Dyck 单词有精确的公式和简短的代数母函数恒等式,但它们所构成的整个语言并非正则语言。前缀 ( 为非负整数)两两可被后缀 区分:只有指数恰好匹配,才能得到平衡且非负的单词。因此,自动机笔记中已证明的有限指标判据排除了有限状态识别器。计数公式与有界记忆的识别算法是不同的数学对象。
概念视角组合
首次返回保留了由两个较小对象构成的有序对
这个分解包含内部部分和随后的部分,而不是由若干分量构成的无序集合。这就是普通级数相乘时无需阶乘除数、而且左右树结构至关重要的原因。每个对象都带有可唯一还原的分裂,因此递推式的相等记录的是一个双射,而不是数值上的巧合。
常见错误
反例模式
总数平衡且第一步向上仍然不够
半长为二时,有六个单词含两个上升步和两个下降步,但只有 和 是 Dyck 单词。单词 以上升步开始并终止于零,但它的第三个前缀的高度为负一。非负性必须在每个前缀上成立,而不只是在第一个和最后一个前缀上成立。反射所计数的,正是这些中间出现的失败。
常见错误
(把平面树个数除以二来忘记左右)
不要把平面树的个数除以二来抹去左右顺序:不同的形状具有不同的对称性。交换根的两棵子树时, 的形状不变, 的形状却改变了,所以平面树个数并不是无序形状个数的固定倍数。
常见错误
(在总数相等时使用严格公式)
不要在上升步与下降步总数相等且为正时使用严格公式,因为在最后的零高度处,严格正性必然失效。当 时没有严格投票单词,而公式要求 。
常见错误
(以解析方式选取平方根符号)
形式平方根的选取由常数项和允许的幂次决定,而不是假设一个尚未引入的解析极限。若取 ,分子常数项为 ,除以 便会产生负次幂 。
总结
首次到达的反射把含禁止前缀的单词转化为无限制的终点计数,从而证明了弱与严格投票公式及卡特兰闭式。首次返回给出有序分解、二次形式级数,以及树与括号化的可逆编码。多边形三角剖分遵循同样的有根分裂,并配有精确的空区域约定。
练习
快速检查
(求含五个上升步和三个下降步的弱投票单词与严格投票单词的个数。)
给出两个整数计数,并指出共同的无限制总数。
解答 · 答案
无限制的总数为 。弱正性给出 ,严格正性给出 。两种计算所数的都是固定步数总数的单词。差值记录的是开始之后曾触及零的单词,弱正性允许这类单词,严格正性则排除它们。
快速检查
(在半长为五的 Dyck 单词中,求首次返回发生在四步之后的单词个数,以及仅在末尾才首次返回的单词个数。)
把返回时刻转换为 中内部部分的半长。
解答 · 答案
在第 步首次返回,意味着内部 Dyck 单词的半长为 。四步给出 ,所以个数为 。仅在末尾(第十步)首次返回,给出 ,所以个数为 。这些是总数 中互不相交的子族;其他返回时刻提供递推式中其余的项。
快速检查
(具有三个内部顶点的无序有根满二叉树形状有多少种?解释为什么把平面树的个数除以二是错误的。)
对根的分裂进行分类,并考虑交换相同子树的情形。
解答
根要么在两棵子树中各有一个内部顶点,得到一种平衡形状;要么有一个叶子和一棵含两个内部顶点的子树。后一棵子树只有一种无序形状,所以它再给出一种形状。无序形状共有两种。
平衡形状只给出一种平面形状,因为交换其相同的子形状不会改变任何东西。不平衡形状给出四种平面形状:选择根的哪一侧是叶子,以及其内部子顶点的哪一侧继续延伸。因此五种平面形状在两种无序形状上的重数是一和四,而不是公共因子二。统一除以二无论在算术上还是作为计数论证都是行不通的。