来源与问题
原笔记未记录具体参考书页。问题是如何把计数递推改写为系数恒等式。以下保留Fibonacci、分拆和标号结构例子;普通形式运算与含有 、 的公式分别说明系数环条件。
幂级数与组合数学:母函数方法
1. 简介
组合计数问题常把数列 打包成一个幂级数(母函数),再借助代数与分析运算统一求出 、证明恒等式、求解递推。这里幂级数通常只看系数、不要求收敛,故称形式幂级数。
2. 形式幂级数
2.1 定义与环结构
设 为交换含幺环(常用 )。形式幂级数环 的元素为
加法逐项,乘法用 Cauchy 乘积:
2.2 形式的观点
这里不涉及收敛与 ,只关心系数的代数关系,因此 等恒等式可以“形式地”使用。
2.3 基本运算
可逆当且仅当 是 的单位。必要性看乘积常数项 ;充分性逐阶解
只有系数环为域时,才能把“单位”简写为“非零”;例如 在 不可逆。单位的角色可与局部化中“让指定元素成为单位”比较,不能把两种构造混为一谈。
形式求导在任意交换环上可定义。若 ,则 每个系数只涉及有限项,故复合良定义;一般非零常数项不能直接代入一个任意形式无穷级数。
3. 两类母函数
3.1 普通母函数(OGF)
3.2 指数母函数(EGF)
以下含阶乘分母的指数母函数、形式指数以及§7的反演公式,取系数在 -代数中,例如 或 ;仅有特征0但不能除以整数的环仍不够。
选择
OGF常用于无标号计数,EGF常用于标号结构,但这不是排他的分类。EGF乘法中,系数对应 ,二项系数负责把 个标号分给两个部分;不是简单地“去掉所有标号影响”。
4. 基本工具与常见恒等式
这里 为整数,二项式式中的 为整数。其中 的系数 正是“ 类对象可重复选取”的组合数。
5. 例子
5.1 斐波那契数列
设 ,。由 得
部分分式后即得 Binet 公式
5.2 整数分拆
设 为把 分成无序正整数之和的方法数,则
约定 。这个乘积展开对应“每个正整数 可被选用任意多次”。对于固定次数 , 的因子只贡献常数项,所以形式无穷乘积良定义,无须先证明解析收敛。
5.3 递推与卷积
母函数乘法对应两个计数对象的“拼接”(卷积),例如 给出 。
6. 指数母函数与标号结构
排列的 EGF 为
设 是一类标号组件的EGF,组件只占正数个标号(),且每个大小只有有限多个结构。由互不相交的标号块组成有序组件列时, 个组件贡献 ,求和得 ;组成无序组件集合时再除以 ,得到 。非空条件保证对固定总大小只需有限个组件数。
7. Lagrange 反演公式
在上述 -代数中,取 为单位,方程 在 中有唯一解。对整数 ,系数公式为
用途
用于求反函数系数、树的计数(如 Cayley 公式)等递归问题;详见 Lagrange 反演公式。
8. 总结
| 母函数 |
适用范围 |
典型恒等式 |
| 普通母函数 OGF |
无标号结构 |
|
| 指数母函数 EGF |
有标号结构 |
|
相关笔记