组合计数的符号方法

形式陈述

符号方法从组合类之间的结构同构或无歧义规格出发。对无标号类，基本字典用普通生成函数表示，包括

\mathcal A=\mathcal B\uplus\mathcal C \Longrightarrow A(z)=B(z)+C(z),

\mathcal A=\mathcal B\times\mathcal C \Longrightarrow A(z)=B(z)C(z).

对标号类，第二式把乘积理解为标签集的互补划分，并使用指数生成函数。进一步的

\operatorname{SEQ},\quad \operatorname{SET},\quad \operatorname{CYC}

分别编码有序列、无序组件集与循环排列；标号与无标号版本的对称性不同，必须使用各自的翻译公式。

“规格”必须给每个结果对象唯一的构造历史，或明确用商与循环指标处理多重表示。递归规格还应在大小方向上良基，使每个系数能由较小系数确定。对于无限 SEQ、SET、CYC 或物种代入，通常要求组件类没有大小零对象；否则同一总大小可能容纳任意多个零大小组件，局部有限性失效。

直觉

符号方法不是看到一个生成函数后猜测组合解释，而是从可逆分解开始：先说明怎样把对象唯一拆开，再把拆法翻译成代数。加法来自互斥选择，乘法来自独立组件，复合来自用一种结构替换另一种结构的原子。每个函数等式背后都应有一份“拆开—重组互为逆”的见证。

这种顺序很重要。若同一对象能由两个分支生成，直接相加会重复计数；若组件排列不该区分，直接使用 SEQ 会多计；若无标号对象有旋转或置换对称，照搬标号的指数公式又会漏掉稳定子。符号只是压缩过的结构证明，不是免除证明的快捷记号。

例子与边界

设 $\mathcal T$ 为非空平面根树，大小是顶点数。删除根后，根的子树从左到右形成一个可能为空的序列，因此有唯一规格

\mathcal T=\mathcal Z\times\operatorname{SEQ}(\mathcal T).

转成 OGF 得

T(z)=\frac{z}{1-T(z)}, \qquad T(z)=\frac{1-\sqrt{1-4z}}2.

由Lagrange 反演或二项式展开，

[z^n]T(z)=\frac1n\binom{2n-2}{n-1}=C_{n-1}.

这不是换数字的例子：根的有序子树序列给出几何级数，顶点原子给出因子 $z$ ，唯一分解给出方程，系数则准确回到含 $n$ 个顶点的平面根树。

若改成无序根树，子树不再组成 SEQ，而是无标号多重集合；公式不再是 $z/(1-T)$ ，必须出现 $T(z^k)$ 的 Pólya 修正。仅删除“平面”二字就会改变整个生成函数，这正显示规格中的结构限定不可省略。

推论与应用

符号方法把计数流程分为三个可核查阶段：建立组合规格，翻译为形式生成函数方程，最后提取系数。线性规格常给有理函数，树状递归常给代数或隐式函数，SET 与 CYC 常引入指数、对数或循环指标。参数可用额外变量标记，从同一规格得到联合分布。

形式方程只保证精确系数关系。若要估计 $[z^n]A(z)$ ，还须证明相应级数具有正收敛半径并研究其复奇点；这一步由解析生成函数与奇点分析承担。反之，解析方法若没有正确规格提供的函数，也无法修复早先的重复计数。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapters I–II, symbolic methods for unlabelled and labelled classes。
Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, 2nd ed., Addison-Wesley, 2013, Chapter 3。
Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999, Chapter 5, trees and Lagrange inversion。