← 全部笔记

数学分析

幂级数在组合数学中的应用

文章目录

来源与问题 原笔记未记录具体参考书页。问题是如何把计数递推改写为系数恒等式。以下保留Fibonacci、分拆和标号结构例子;普通形式运算与含有 1/n!1/n!、1/n1/n 的公式分别说明系数环条件。

幂级数与组合数学:母函数方法

1. 简介

组合计数问题常把数列 (an)(a_n) 打包成一个幂级数(母函数),再借助代数与分析运算统一求出 ana_n、证明恒等式、求解递推。这里幂级数通常只看系数、不要求收敛,故称形式幂级数。

2. 形式幂级数

2.1 定义与环结构

设 K\mathbb K 为交换含幺环(常用 Z,Q,C\mathbb{Z},\mathbb{Q},\mathbb{C})。形式幂级数环 K[ ⁣[x] ⁣]\mathbb{K}[\![x]\!] 的元素为

A(x)=∑n≥0anxn,A(x)=\sum_{n\ge0}a_nx^n,

加法逐项,乘法用 Cauchy 乘积:

A(x)B(x)=∑n≥0(∑k=0nakbn−k)xn.A(x)B(x)=\sum_{n\ge0}\Bigl(\sum_{k=0}^{n}a_kb_{n-k}\Bigr)x^n.

2.2 形式的观点

这里不涉及收敛与 ∣x∣|x|,只关心系数的代数关系,因此 1/(1−x)=∑xn1/(1-x)=\sum x^n 等恒等式可以“形式地”使用。

2.3 基本运算

AA 可逆当且仅当 a0a_0 是 K\mathbb K 的单位。必要性看乘积常数项 a0b0=1a_0b_0=1;充分性逐阶解 b0=a0−1,bn=−a0−1∑k=1nakbn−k.b_0=a_0^{-1},\qquad b_n=-a_0^{-1}\sum_{k=1}^n a_kb_{n-k}. 只有系数环为域时,才能把“单位”简写为“非零”;例如 2+x2+x 在 Z[ ⁣[x] ⁣]\mathbb Z[\![x]\!] 不可逆。单位的角色可与局部化中“让指定元素成为单位”比较,不能把两种构造混为一谈。

形式求导在任意交换环上可定义。若 ϕ(0)=0\phi(0)=0,则 A(ϕ(x))A(\phi(x)) 每个系数只涉及有限项,故复合良定义;一般非零常数项不能直接代入一个任意形式无穷级数。

3. 两类母函数

3.1 普通母函数(OGF)

G(x)=∑n≥0anxn.G(x)=\sum_{n\ge0}a_nx^n.

3.2 指数母函数(EGF)

以下含阶乘分母的指数母函数、形式指数以及§7的反演公式,取系数在 Q\mathbb Q-代数中,例如 Q\mathbb Q 或 C\mathbb C;仅有特征0但不能除以整数的环仍不够。

G^(x)=∑n≥0anxnn!.\widehat G(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}.

选择 OGF常用于无标号计数,EGF常用于标号结构,但这不是排他的分类。EGF乘法中,系数对应 ∑k(nk)akbn−k\sum_k\binom nk a_kb_{n-k},二项系数负责把 nn 个标号分给两个部分;不是简单地“去掉所有标号影响”。

4. 基本工具与常见恒等式

11−x=∑n≥0xn,1(1−x)k=∑n≥0(n+k−1k−1)xn,\frac{1}{1-x}=\sum_{n\ge0}x^n,\qquad \frac{1}{(1-x)^k}=\sum_{n\ge0}\binom{n+k-1}{k-1}x^n,

ex=∑n≥0xnn!,(1+x)n=∑k=0n(nk)xk.e^x=\sum_{n\ge0}\frac{x^n}{n!},\qquad (1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k.

这里 k≥1k\ge1 为整数,二项式式中的 n≥0n\ge0 为整数。其中 1(1−x)k\frac{1}{(1-x)^k} 的系数 (n+k−1k−1)\binom{n+k-1}{k-1} 正是“kk 类对象可重复选取”的组合数。

5. 例子

5.1 斐波那契数列

设 F(x)=∑n≥0FnxnF(x)=\sum_{n\ge0}F_nx^n,F0=0, F1=1F_0=0,\,F_1=1。由 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} 得

F(x)=x1−x−x2.F(x)=\frac{x}{1-x-x^2}.

部分分式后即得 Binet 公式

Fn=15[(1+52)n−(1−52)n].F_n=\frac{1}{\sqrt5}\left[\Bigl(\tfrac{1+\sqrt5}{2}\Bigr)^n-\Bigl(\tfrac{1-\sqrt5}{2}\Bigr)^n\right].

5.2 整数分拆

设 p(n)p(n) 为把 nn 分成无序正整数之和的方法数,则

∑n≥0p(n)xn=∏k≥111−xk.\sum_{n\ge0}p(n)x^n=\prod_{k\ge1}\frac{1}{1-x^k}.

约定 p(0)=1p(0)=1。这个乘积展开对应“每个正整数 kk 可被选用任意多次”。对于固定次数 nn,k>nk>n 的因子只贡献常数项,所以形式无穷乘积良定义,无须先证明解析收敛。

5.3 递推与卷积

母函数乘法对应两个计数对象的“拼接”(卷积),例如 1(1−x)2=∑n≥0(n+1)xn\frac{1}{(1-x)^2}=\sum_{n\ge0}(n+1)x^n 给出 ∑n≥0nxn=x(1−x)2\sum_{n\ge0}nx^n=\frac{x}{(1-x)^2}。

6. 指数母函数与标号结构

排列的 EGF 为

∑n≥0n!xnn!=11−x.\sum_{n\ge0}n!\frac{x^n}{n!}=\frac{1}{1-x}.

设 A(x)A(x) 是一类标号组件的EGF,组件只占正数个标号(A(0)=0A(0)=0),且每个大小只有有限多个结构。由互不相交的标号块组成有序组件列时,kk 个组件贡献 A(x)kA(x)^k,求和得 1/(1−A(x))1/(1-A(x));组成无序组件集合时再除以 k!k!,得到 exp⁡(A(x))\exp(A(x))。非空条件保证对固定总大小只需有限个组件数。

7. Lagrange 反演公式

在上述 Q\mathbb Q-代数中,取 ϕ(0)\phi(0) 为单位,方程 w(z)=zϕ(w(z))w(z)=z\phi(w(z)) 在 zK[ ⁣[z] ⁣]z\mathbb K[\![z]\!] 中有唯一解。对整数 n≥1n\ge1,系数公式为

[zn]w(z)=1n[un−1]ϕ(u)n.[z^n]w(z)=\frac1n[u^{n-1}]\phi(u)^n.

用途 用于求反函数系数、树的计数(如 Cayley 公式)等递归问题;详见 Lagrange 反演公式。

8. 总结

母函数 适用范围 典型恒等式
普通母函数 OGF 无标号结构 ∑xn=1/(1−x)\sum x^n=1/(1-x)
指数母函数 EGF 有标号结构 ∑n!xnn!=1/(1−x)\sum n!\dfrac{x^n}{n!}=1/(1-x)

相关笔记