动机
计数问题常常在去掉对象的最后一部分之后变得更简单。剩下的对象更小,因此这种分解给出一个递推关系。递推关系还不是封闭形式的答案:它的初始值与适用范围同样重要。生成函数把整个序列打包起来,使得下标的移位变成乘以一个形式变量。
定义
定义 3.1.1
(形式级数与递推关系)
对于实数或复数上的序列 ,其普通生成函数是形式级数 。两个形式级数相等,指它们的每一个系数都相等。乘积采用有限卷积法则
阶为 的常系数齐次线性递推关系是指:当 时 ,并同时给定 。
“形式”的意思是:我们既不先取定 的数值,也不过问分析意义上的收敛性。乘积的每一个系数都只涉及有限多项。常数项非零的形式级数有唯一的乘法逆元,可以从零次项开始逐次向上求解各次系数,递归地得到。
定理/命题
定理 3.1.2
(初始值决定递推关系的解)
具有上述形式的递推关系与 个初始值恰好决定一个序列。它的生成函数满足
特别地,它的生成函数作为形式级数是有理的。
定理 3.1.3
(两个相异的特征根)
若对 有 ,且 有相异的非零根 ,则存在唯一的常数 ,使得对每个 都有 。它们由 与 确定。
证明思路
证明
(存在性、唯一性与分子多项式)
递推关系解的存在性,由逐项依次定义下一项得到。若两个解在前 项上一致,则由归纳法,它们在其后每一项上也一致,这就证明了唯一性。将 乘以分母多项式。对于次数 ,所得系数为 ;对于 ,它恰好是右边的系数。分母的常数项为 ,所以它在形式意义下可逆。
证明
(构造线性组合,再援引唯一性)
对于特征根定理,序列 与 各自由其定义二次方程而满足该递推关系。关于 的两个方程,其行列式 非零。它们的线性组合具有正确的初始值,因此由唯一性可知它就等于所求序列。这个证明并没有去猜测所有解都具有所示形式;它构造出一个解,再援引唯一性。
证明透视
相异根在哪里用到
这个证明有两个相互独立的部分。第一,每个几何序列都是递推关系的解:对 ,
而递推关系是线性的,所以每个组合 也是解。这部分完全没有用到 。第二,必须能配合初始值:方程组 、 的行列式是 ,相异性只在这里用到。行列式非零,对每组 都恰好给出一对 ;若两对常数都表示该序列,它们在 处解同一个非奇异方程组,所以相等。论证最后不是靠计算更多项来完成,而是经由第一个定理:该组合与所给序列是前两项相同的两个解,因此对每个 都相等。
当两个根重合时,两个指数序列是同一个序列,上述论证便不再适用。例如,递推关系 说明一阶差分为常数,从而 。多出来的因子 来自一个真正不同的第二个解。
反例模式
重根使初始值无法配合
断言:二阶递推关系的每个解,都是其特征根之幂的线性组合。对 ,特征多项式为 ,唯一的根是 ,而它的幂的任何组合都是常数 。初始值 、 要求同时有 与 ,这不可能。然而该递推关系有解 ;例如 。此时行列式 为零,失效的正是这个假设。修正:若 是非零重根,即 、,则序列 是第二个解,因为 。对 ,初始条件为 与 ,这个方程组的行列式是 。
例题详解
例题 3.1.4
(不含相邻两个 1 的二进制串)
设 为不含子块 的长度为 的二进制串的个数。空串有一个,所以 ,并且 。对于 ,以 结尾的串,是在一个合乎要求的长度为 的串后面添上 得到的。以 结尾的串必定以 结尾,它们由合乎要求的长度为 的串得到。这两种情形互不相交且穷尽所有可能,所以 。于是 ,并且 。
例题 3.1.5
(一个非齐次递推关系)
设 ,且对 有 。令 。则 且 ,所以 。检验 ,两边都给出 。这一代换消去了强迫项;齐次情形的特征公式不能简单地忽略该项。
例题 3.1.6
(在重复因子之后提取系数)
形式几何级数满足 。将它平方并利用卷积,得到 ,因为该系数计数的是和为 的非负整数对。因此,对 有 ,而常数项为 。
不依赖收敛性假设的形式代数
形式生成函数是对系数的一份记录,起初并不是一个数值函数。使用无穷记号是合理的,因为和或积的每一个所需系数,都只由有限多个输入确定。对于乘积,给定次数处的系数只用到次数相加等于该次数的那些次数对。因此,即使没有任何一个变量的数值能使原来两个级数同时收敛,卷积公式依然是良定义的。
逆元的存在性可以用同样的有限推理来证明。在零次项处,乘积方程迫使逆元的常数项确定下来。在一次项处,它迫使下一个系数确定,且只用到已经确定的系数。此后每一次项都给出一个线性方程,其首项标量相同且非零。于是逆元存在且唯一,整个过程没有取任何分析意义上的极限。如果原级数的常数项为零,则零次项处的乘积不可能等于一,因此这样的逆元不存在。
这一观点解释了递推问题中出现的分母。它们的常数项是一,所以除法从一开始就在形式意义下成立。如果提出的是分析性问题,则之后可以再研究数值收敛性,但按系数计数的论证不应依赖于在某个数值点上未经证明的代入。
初始条件是下标移位的边界项
将生成函数乘以变量,会使其系数序列后移一位,并在开头插入零。递推关系的移位并不会自动插入实际的初始值;它们必须另行处理。这正是分子多项式的来源,也说明了为什么两个序列可以满足同一个递推关系,却有不同的生成函数。
可靠的推导方法是:先在递推关系成立的下标处把它乘上去,仅对这些下标求和,并在化简之前把每个截断级数明确写出。这样,每一个被省略的初始项都清晰可见。一旦掌握了这一模式,定理中的一般公式便能高效地完成这项记账工作。如果某个分子看起来意外地简单,应当把它的前几个系数与所给的初始值逐一核对,而不要假定所有边界项都已消失。
这里的棋盘铺法序列计算用长度一和二的砖铺板的方法:空板有一种铺法,长度一也有一种;移除最后一块便给出同样的两项递推。
不含相邻两个 1 的序列与铺砖序列正好说明了这一区别。它们满足同一个二阶递推关系,但首项不同。因此它们的分母相同,分子却不同。递推关系描述的是更新规则;分子记录的则是从这条更新规则的所有解中选取了哪一个解。单凭其中任何一部分,都无法确定这个计数序列。
有序组装与无序选取
生成函数反映被计数对象的确切结构。假设一个整数总和由大小为一和二的部分构成,这些部分之间不附带任何次序。大小为二的部分的个数唯一地确定了该对象,其余的单位则是大小为一的部分。其生成函数是两个级数的乘积:一个允许任意多个大小为一的部分,另一个允许任意多个大小为二的部分。它的分母是相应两个几何级数分母的乘积。
当总和为五时,这样的无序选取有三种:使用零个、一个或两个大小为二的部分。这与长度为五的板的八种铺法不同,因为铺法记录了砖块的次序。先放一块长度为二的砖再放一块长度为一的砖,与相反次序是不同的铺法,尽管两者每种砖的块数相同。这种不一致并不是生成函数的失败;它说明两个模型计数的是不同的对象。
要直接提取无序情形的系数,可以在零到总和的一半(向下取整)之间选取大小为二的部分的个数。每一种选择都恰好留下一个合法的大小为一的部分的个数。因此答案是该向下取整的一半再加一。这个系数计算是一个有限卷积,为乘法法则提供了另一种具体解释。
由首次回归得到的非线性递推
并非每个有用的递推关系都是线性的。考虑这样的括号平衡串:左、右括号总数相等,且每个前缀中的左括号个数都不少于右括号个数。空串是允许的。非空的这类串以左括号开头。与它配对的右括号,位于第一次回到平衡值零的位置,它把该串唯一地分成内部的一个平衡串与其后的一个平衡串。
若总共有固定数目的括号对,则选定内部的对数就决定了其后的对数。这两个较小的串随后可以独立选取。对所有可能的分割大小,把它们的计数之积求和,便得到一个卷积型递推关系,其中空串的计数等于一。这个分割是唯一的,因为它使用的是首次回到零的位置;若任意选取一个右括号,则得不到同样明确的分解。
用生成函数的语言来说,该级数等于空串情形的一,加上非空情形的变量乘以它自身的平方。变量记录最外层的那一对配对括号。这个方程递归地确定每一个系数:正次数处的系数只依赖于更早的系数。从一开始,零到三对括号的计数依次为一、一、二和五。若要得到封闭公式,还需要进一步的论证;而这一分解本身,无需封闭公式,就已经证明了该递推关系及其含义。
若 计算有 对括号的串,且 ,则上述分解给出 ,以及对 有 ,从而 。
概念视角结构
乘积记录了对象分成两部分
乘积中的卷积系数考虑了将总大小分配给第一个对象与第二个对象的所有方式。只有当原对象能唯一地分解为这样一个有序对时,组合意义上的乘积才有依据。同一个系数法则可以编码两段括号、两个独立的选取,或一个代数递推关系,但在每种情形下都必须另行给出解释。
封闭形式由存在性与唯一性来验证
一个猜想的公式,可能来自巧妙的代换、特征多项式,或生成函数的运算。验证往往比发现简单得多。检查初始值,把所提出的表达式代入每一个有效下标处的递推关系,再援引唯一性。即使启发出这一公式的途径并不严格,这三步论证也能证明该公式。
对于重复的特征根,相异根定理的假设确实不成立。必须另外推导出一个解,或者回到生成函数;仅仅把同一个根赋给两个常数,只会得到一个指数序列。对于非齐次递推关系,在应用齐次情形的唯一性论证之前,必须先包含针对强迫项的一个特解。这是扩展该方法的两个不同原因,因此不应把它们合并为一个含糊的例外。
最后,递推关系的阶并不一定是每个选定序列可能的最小阶。特殊的初始值可能使封闭形式中的某一项消失,从而允许存在更低阶的关系。所给出的递推关系仍然正确地确定该序列。区分有效的递推关系与最小的递推关系,可以避免作出超出计算所能证明的断言。
常见错误
常见错误
(在第一个有效下标之前套用递推关系)
从 起成立的递推关系,不能代入 ,除非像 这样的项已另行定义并给出理由。对不含 的串,若设 并在 处套用 ,会得到 ;但串 与 给出 。在生成函数的计算中保留初始多项式,可以避免这类下标错误。
常见错误
(没有双射就去掉最后一个符号)
组合递推关系需要一个双射的分解。如果允许的扩展方式的数目取决于剩余的串,那么只说“去掉最后一个符号”是不够的。在不含 的例子中,以 结尾的合乎要求的串只能再添 ,所以 并不等于 :已有 。把结尾 与结尾 分开,就使这种依赖关系变得明确。
常见错误
(把数值代入形式恒等式)
形式恒等式不会自动使在级数解析收敛域之外的数值代入变得合理。若在 处解读形式恒等式 ,便会断言 ,作为数值求和这毫无意义。该恒等式是关于系数的陈述;要代入数值,须另有收敛性论证。
总结
一个分解提供一个递推关系及其初始值。形式生成函数把移位变成多项式乘法,初始项出现在分子中。唯一性则提供了一种清晰的方法,来验证所提出的封闭形式。
练习
快速检查
(计数用长度为一和二的砖块铺满长度为 的板的铺法数。求其生成函数,并求 时的计数。)
空板有一种铺法。
解答 · 答案
设 。对于 ,去掉最后一块长度为一或长度为二的砖,得到 ,其中两种情形互不相交,且可以唯一地还原。因此 。数值 说明 。
快速检查
(解 ,其中 、,并求其生成函数。)
利用一阶差分,或利用一般的生成函数恒等式。
解答 · 答案
由递推关系得 ,所以每个一阶差分都是 。因此 。生成函数为 。分子也可以直接由 得到。
快速检查
(已知 ,用 计算 ,并说明下标为 的项计数什么。)
解答 · 答案
取 ,得 。下标为 的项计数这样的四对括号串:其第一对括号(在首次回到零处闭合)内含 对,其后跟着一个含其余 对的平衡串。这四种情形互不相交且涵盖每个串,所以把各乘积相加。