跳转至

# 符号化方法

符号化方法（symbolic method）是将组合对象快速转换成生成函数的一种方法，我们将考虑对于集合上定义的特定运算，然后导出其对应的生成函数的运算．

我们称一个组合类（或简称为类）为 (A,| ⋅|)(A,|⋅|)，其中 A A 为组合对象的集合，函数 | ⋅||⋅| 将每一个组合对象映射为一个非负整数，一般称为大小函数．需要注意的是这个非负整数不能是无限大的．例如对于字符集为 {0,1}{0,1} 的字符串，可以将字符串的长度设置为其大小函数；对于树或图可将节点的数量设置为其大小函数，注意这并非绝对，也可能将某些特定节点的大小函数设置为 0 0 等．

本文是基于 Analytic Combinatorics 一书第一章的简化．

## 无标号体系

在无标号体系中将使用普通生成函数（OGF）．对于集合 A A 其对应 OGF 记为

𝐴(𝑧)=∑𝛼∈A 𝑧|𝛼|=∑𝑛≥0 𝑎 𝑛 𝑧 𝑛 A(z)=∑α∈A z|α|=∑n≥0 a n z n

我们约定使用同一组的字母表示同一个类对应的生成函数等，例如用 𝑎 𝑛 a n 表示 [𝑧 𝑛]𝐴(𝑧)[z n]A(z) 即 𝐴(𝑧)A(z) 中 𝑧 𝑛 z n 的系数，用 A 𝑛 A n 表示 A A 中大小函数为 𝑛 n 的对象的集合（所以 𝑎 𝑛 =c a r d⁡(A 𝑛)a n=card⁡(A n) 其中 c a r d card 为基数（cardinality））．

本文将不讨论可容许性（admissibility），读者可参考文献中的内容．

下面将引入两种特殊的组合类和组合对象：

- 记 𝜖 ϵ 为中性对象（neutral object）和 E ={𝜖}E={ϵ} 为中性类（neutral class），中性对象的大小为 0 0，中性类的 OGF 为 𝐸(𝑧) =1 E(z)=1．
- 记 ∘∘ 或 ∙∙ 为原子对象（atom object）和 Z∘ ={ ∘}Z∘={∘} 或 Z∙ ={ ∙}Z∙={∙} 或简写为 Z Z 为原子类（atom class），原子对象的大小为 1 1，原子类的 OGF 为 𝑍(𝑧) =𝑧 Z(z)=z．

对于两个组合类 A A 和 B B 在组合意义上同构记为 A =B A=B 或 A ≅B A≅B，但仅当该同构不平凡时才使用后者的记号．

我们有

A≅E×A≅A×E A≅E×A≅A×E

其中 ×× 为二元运算，表示集合的笛卡尔积．

### 集合的（不相交）并构造

对于类 A A 和 B B 的并记为

A+B=(E 1×A)+(E 2×B)A+B=(E 1×A)+(E 2×B)

如此定义可以不违背集合论中集合不相交的要求，我们可以想象成将 A A 中的对象染色成红色，将 B B 中的对象染色成蓝色．

对应 OGF 为

𝐴(𝑧)+𝐵(𝑧)A(z)+B(z)

考虑

𝐴(𝑧)+𝐵(𝑧)=∑𝛼∈A 𝑧|𝛼|+∑𝛽∈B 𝑧|𝛽|=∑𝑛≥0(𝑎 𝑛+𝑏 𝑛)𝑧 𝑛 A(z)+B(z)=∑α∈A z|α|+∑β∈B z|β|=∑n≥0(a n+b n)z n

对应形式幂级数的加法．

### 集合的笛卡尔积构造

对于类 A A 和 B B 的笛卡尔积记为

A×B={(𝛼,𝛽)∣𝛼∈A,𝛽∈B}A×B={(α,β)∣α∈A,β∈B}

对应 OGF 为

𝐴(𝑧)⋅𝐵(𝑧)A(z)⋅B(z)

我们定义 (𝛼,𝛽)(α,β) 的大小为其组成部分的大小之和，那么显然也有

𝛾=(𝛼 1,𝛼 2,…,𝛼 𝑛)⟹|𝛾|=|𝛼 1|+|𝛼 2|+⋯+|𝛼 𝑛|γ=(α 1,α 2,…,α n)⟹|γ|=|α 1|+|α 2|+⋯+|α n|

所以

𝐴(𝑧)⋅𝐵(𝑧)=(∑𝛼∈A 𝑧|𝛼|)(∑𝛽∈B 𝑧|𝛽|)=∑(𝛼,𝛽)∈(A×B)𝑧|𝛼|+|𝛽|=∑𝑛≥0∑𝑖+𝑗=𝑛 𝑎 𝑖 𝑏 𝑗 𝑧 𝑛 A(z)⋅B(z)=(∑α∈A z|α|)(∑β∈B z|β|)=∑(α,β)∈(A×B)z|α|+|β|=∑n≥0∑i+j=n a i b j z n

对应形式幂级数的乘法．

### 集合的 Sequence 构造

Sequence 构造生成了所有可能的组合．

例
S E Q⁡({𝑎})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯S E Q⁡({𝑎,𝑏})={𝜖}+{𝑎,𝑏}+{(𝑎,𝑏)}+{(𝑏,𝑎)}+{(𝑎,𝑎)}+{(𝑏,𝑏)}+{(𝑎,𝑏,𝑎)}+{(𝑎,𝑏,𝑏)}+{(𝑎,𝑎,𝑏)}+{(𝑏,𝑏,𝑎)}+{(𝑏,𝑎,𝑏)}+{(𝑏,𝑏,𝑏)}+{(𝑎,𝑎,𝑎)}+{(𝑏,𝑎,𝑎)}+⋯SEQ⁡({a})={ϵ}+{a}+{(a,a)}+{(a,a,a)}+⋯SEQ⁡({a,b})={ϵ}+{a,b}+{(a,b)}+{(b,a)}+{(a,a)}+{(b,b)}+{(a,b,a)}+{(a,b,b)}+{(a,a,b)}+{(b,b,a)}+{(b,a,b)}+{(b,b,b)}+{(a,a,a)}+{(b,a,a)}+⋯

可以看到 {(𝑎,𝑏)},{(𝑏,𝑎)}{(a,b)},{(b,a)} 这样组成部分的顺序不同的元素被生成了，可以认为 Sequence 构造生成了有序的组合．

我们定义

S E Q⁡(A)=E+A+(A×A)+(A×A×A)+⋯SEQ⁡(A)=E+A+(A×A)+(A×A×A)+⋯

且要求 A 0 =∅A 0=∅，也就是 A A 中没有大小为 0 0 的对象．

对应 OGF 为

𝑄(𝐴(𝑧))=1+𝐴(𝑧)+𝐴(𝑧)2+𝐴(𝑧)3+⋯=1 1−𝐴(𝑧)Q(A(z))=1+A(z)+A(z)2+A(z)3+⋯=1 1−A(z)

其中 𝑄 Q 为 Pólya 准逆（quasi-inversion）．

例：有序有根树（ordered rooted tree）

我们可以使用 Sequence 构造来定义有序有根树，即孩子之间的顺序有意义的有根树，设该组合类为 T T 那么一棵树为一个根节点和树的 Sequence，即

T={∙}×S E Q⁡(T)T={∙}×SEQ⁡(T)

对应 OGF 为

𝑇(𝑧)=𝑧 1−𝑇(𝑧)T(z)=z 1−T(z)

前几项系数为 `0 1 1 2 5 14 42 132 429 1430 4862 16796`，忽略常数项即 OEIS A000108．

### 集合的 Multiset 构造

Multiset 构造生成了所有可能的组合，但不区分组成部分的元素之间的顺序．

例
M S E T⁡({𝑎})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯M S E T⁡({𝑎,𝑏})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯+{𝑏}+{(𝑎,𝑏)}+{(𝑎,𝑎,𝑏)}+⋯+{(𝑏,𝑏)}+{(𝑎,𝑏,𝑏)}+{(𝑎,𝑎,𝑏,𝑏)}+⋯+⋯MSET⁡({a})={ϵ}+{a}+{(a,a)}+{(a,a,a)}+⋯MSET⁡({a,b})={ϵ}+{a}+{(a,a)}+{(a,a,a)}+⋯+{b}+{(a,b)}+{(a,a,b)}+⋯+{(b,b)}+{(a,b,b)}+{(a,a,b,b)}+⋯+⋯

注意到 {(𝑏,𝑎)},{(𝑎,𝑏,𝑎)}{(b,a)},{(a,b,a)} 在 S E Q⁡({𝑎,𝑏})SEQ⁡({a,b}) 中出现，但在 M S E T⁡({𝑎,𝑏})MSET⁡({a,b}) 没有出现，可以认为 Multiset 生成了无序的组合．

我们定义其递推式为

M S E T⁡({𝛼 0,𝛼 1,…,𝛼 𝑛})=M S E T⁡({𝛼 0,𝛼 1,…,𝛼 𝑛−1})×S E Q⁡({𝛼 𝑛})MSET⁡({α 0,α 1,…,α n})=MSET⁡({α 0,α 1,…,α n−1})×SEQ⁡({α n})

即

M S E T⁡(A)=∏𝛼∈A S E Q⁡({𝛼})MSET⁡(A)=∏α∈A SEQ⁡({α})

且要求 A 0 =∅A 0=∅．或者也可以给出等价的

M S E T⁡(A)=S E Q⁡(A)/𝐑 MSET⁡(A)=SEQ⁡(A)/R

其中 𝐑 R 为等价关系，我们说 (𝛼 1,…,𝛼 𝑛)𝐑(𝛽 1,…,𝛽 𝑛)(α 1,…,α n)R(β 1,…,β n) 当且仅当存在任一置换 𝜎 σ 对于所有 𝑗 j 满足 𝛽 𝑗 =𝛼 𝜎(𝑗)β j=α σ(j)．

对应 OGF 为

E x p⁡(𝐴(𝑧))=∏𝛼∈A(1−𝑧|𝛼|)−1=∏𝑛≥1(1−𝑧 𝑛)−𝑎 𝑛 Exp⁡(A(z))=∏α∈A(1−z|α|)−1=∏n≥1(1−z n)−a n

注意到

l n⁡(1+𝑧)=𝑧 1−𝑧 2 2+𝑧 3 3−⋯=∑𝑛≥1(−1)𝑛−1 𝑧 𝑛 𝑛 ln⁡(1+z)=z 1−z 2 2+z 3 3−⋯=∑n≥1(−1)n−1 z n n

且 𝐴(𝑧) =e x p⁡(l n⁡(𝐴(𝑧)))A(z)=exp⁡(ln⁡(A(z))) 所以

E x p⁡(𝐴(𝑧))=e x p⁡(∑𝑛≥1−𝑎 𝑛⋅l n⁡(1−𝑧 𝑛))=e x p⁡(∑𝑛≥1−𝑎 𝑛⋅∑𝑚≥1−𝑧 𝑛 𝑚 𝑚)=e x p⁡(𝐴(𝑧)1+𝐴(𝑧 2)2+𝐴(𝑧 3)3+⋯)Exp⁡(A(z))=exp⁡(∑n≥1−a n⋅ln⁡(1−z n))=exp⁡(∑n≥1−a n⋅∑m≥1−z n m m)=exp⁡(A(z)1+A(z 2)2+A(z 3)3+⋯)

其中 E x p Exp 为 Pólya 指数，也被称为 Euler 变换．

例题 LOJ 6268. 分拆数

题意：令 𝑓(𝑛)f(n) 表示将 𝑛 n 进行分拆的方案数，求 𝑓(1),𝑓(2),…,𝑓(1 0 5)f(1),f(2),…,f(10 5) 对 9 9 8 2 4 4 3 5 3 998244353 取模的值．

解：设全体正整数类为 I I，那么 I =S E Q≥1⁡(Z) =Z ×S E Q⁡(Z)I=SEQ≥1⁡(Z)=Z×SEQ⁡(Z)（下标 ≥1≥1 为有限制的构造，见后文）．所求即

M S E T⁡(I)MSET⁡(I)

对应 OGF 前几项系数为 `1 2 3 5 7 11 15 22 30 42`（忽略常数项）即 OEIS A000041．

例题 洛谷 P4389 付公主的背包

题意：给出 𝑛 n 种体积分别为 𝑣 1,…,𝑣 𝑛 v 1,…,v n 的商品和正整数 𝑚 m，求体积为 1,2,…,𝑚 1,2,…,m 的背包装满的方案数（商品数量不限，有同体积的不同种商品）对 9 9 8 2 4 4 3 5 3 998244353 取模的值．约定 1 ≤𝑛,𝑚 ≤1 0 5 1≤n,m≤10 5 且 1 ≤𝑣 𝑖 ≤𝑚 1≤v i≤m．

解：设商品的组合类为 A A，所求即 M S E T⁡(A)MSET⁡(A) 对应 OGF 的系数．

例题 洛谷 P5900 无标号无根树计数

题意：求出 𝑛 n 个节点的无标号无根树的个数对 9 9 8 2 4 4 3 5 3 998244353 取模的值．约定 1 ≤𝑛 ≤2 ×1 0 5 1≤n≤2×10 5．

解：设无标号有根树的组合类为 T T，那么

T={∙}×M S E T⁡(T)T={∙}×MSET⁡(T)

根据 Richard Otter 的论文 The Number of Trees 中的描述，对应无根树的 OGF 为

𝑇(𝑧)−1 2 𝑇 2(𝑧)+1 2 𝑇(𝑧 2)T(z)−1 2 T 2(z)+1 2 T(z 2)

前几项系数为 `1 1 1 2 3 6 11 23 47 106`（忽略常数项）即 OEIS A000055．

### 集合的 Powerset 构造

Powerset 构造生成了所有子集．

例
P S E T⁡({𝑎})={𝜖}+{𝑎}P S E T⁡({𝑎,𝑏})={𝜖}+{𝑎}+{𝑏}+{(𝑎,𝑏)}P S E T⁡({𝑎,𝑏,𝑐})={𝜖}+{𝑎}+{𝑏}+{(𝑎,𝑏)}+{𝑐}+{(𝑎,𝑐)}+{(𝑏,𝑐)}+{(𝑎,𝑏,𝑐)}PSET⁡({a})={ϵ}+{a}PSET⁡({a,b})={ϵ}+{a}+{b}+{(a,b)}PSET⁡({a,b,c})={ϵ}+{a}+{b}+{(a,b)}+{c}+{(a,c)}+{(b,c)}+{(a,b,c)}

我们定义其递推式为

P S E T⁡({𝛼 0,𝛼 1,…,𝛼 𝑛})=P S E T⁡({𝛼 0,𝛼 1,…,𝛼 𝑛−1})×({𝜖}+{𝛼 𝑛})PSET⁡({α 0,α 1,…,α n})=PSET⁡({α 0,α 1,…,α n−1})×({ϵ}+{α n})

即

P S E T⁡(A)≅∏𝛼∈A({𝜖}+{𝛼})PSET⁡(A)≅∏α∈A({ϵ}+{α})

且要求 A 0 =∅A 0=∅．

对应 OGF 为

―――E x p(𝐴(𝑧))=∏𝛼∈A(1+𝑧|𝛼|)=∏𝑛≥1(1+𝑧 𝑛)𝑎 𝑛=e x p⁡(∑𝑛≥1 𝑎 𝑛⋅l n⁡(1+𝑧 𝑛))=e x p⁡(∑𝑛≥1 𝑎 𝑛⋅∑𝑚≥1(−1)𝑚−1 𝑧 𝑛 𝑚 𝑚)=e x p⁡(𝐴(𝑧)1−𝐴(𝑧 2)2+𝐴(𝑧 3)3−⋯)Exp―(A(z))=∏α∈A(1+z|α|)=∏n≥1(1+z n)a n=exp⁡(∑n≥1 a n⋅ln⁡(1+z n))=exp⁡(∑n≥1 a n⋅∑m≥1(−1)m−1 z n m m)=exp⁡(A(z)1−A(z 2)2+A(z 3)3−⋯)

其中 ―――E x p Exp― 为 Pólya 指数·改．

容易发现 P S E T⁡(A) ⊂M S E T⁡(A)PSET⁡(A)⊂MSET⁡(A)．

### 集合的 Cycle 构造

Cycle 构造生成了所有可能的组合，但不区分仅轮换不同的组合．

我们定义为

C Y C⁡(A)=(S E Q⁡(A)∖{𝜖})/𝐒 CYC⁡(A)=(SEQ⁡(A)∖{ϵ})/S

其中 𝐒 S 为等价关系，我们说 (𝛼 1,…,𝛼 𝑛)𝐒(𝛽 1,…,𝛽 𝑛)(α 1,…,α n)S(β 1,…,β n) 当且仅当存在任一循环移位 𝜏 τ 对于所有 𝑗 j 都满足 𝛽 𝑗 =𝛼 𝜏(𝑗)β j=α τ(j)．

例

为了简便我们令 𝚊,𝚋 a,b 均为大小为 1 1 的字符，这里仅列举大小为 3 3 和 4 4 的字符串：

C Y C⁡({𝚊,𝚋})3={𝚊 𝚊 𝚊}+{𝚊 𝚊 𝚋}+{𝚊 𝚋 𝚋}+{𝚋 𝚋 𝚋}CYC⁡({a,b})3={aaa}+{aab}+{abb}+{bbb}

其中 𝚊 𝚊 𝚋 𝐒 𝚋 𝚊 𝚊 𝐒 𝚊 𝚋 𝚊 aab S baa S aba 只保留其一，同样的 𝚊 𝚋 𝚋 𝐒 𝚋 𝚊 𝚋 𝐒 𝚋 𝚋 𝚊 abb S bab S bba 只保留其一．

C Y C⁡({𝚊,𝚋})4={𝚊 𝚊 𝚊 𝚊}+{𝚊 𝚊 𝚊 𝚋}+{𝚊 𝚊 𝚋 𝚋}+{𝚊 𝚋 𝚋 𝚋}+{𝚋 𝚋 𝚋 𝚋}+{𝚊 𝚋 𝚊 𝚋}CYC⁡({a,b})4={aaaa}+{aaab}+{aabb}+{abbb}+{bbbb}+{abab}

其中 𝚊 𝚊 𝚊 𝚋 𝐒 𝚋 𝚊 𝚊 𝚊 𝐒 𝚊 𝚋 𝚊 𝚊 𝐒 𝚊 𝚊 𝚋 𝚊 aaab S baaa S abaa S aaba，𝚊 𝚊 𝚋 𝚋 𝐒 𝚋 𝚊 𝚊 𝚋 𝐒 𝚋 𝚋 𝚊 𝚊 𝐒 𝚊 𝚋 𝚋 𝚊 aabb S baab S bbaa S abba，𝚊 𝚋 𝚋 𝚋 𝐒 𝚋 𝚊 𝚋 𝚋 𝐒 𝚋 𝚋 𝚊 𝚋 𝐒 𝚋 𝚋 𝚋 𝚊 abbb S babb S bbab S bbba 和 𝚊 𝚋 𝚊 𝚋 𝐒 𝚋 𝚊 𝚋 𝚊 abab S baba．

对应 OGF 为

L o g⁡(𝐴(𝑧))=∑𝑛≥1 𝜑(𝑛)𝑛 l n⁡1 1−𝐴(𝑧 𝑛)Log⁡(A(z))=∑n≥1 φ(n)n ln⁡1 1−A(z n)

其中 𝜑 φ 为 Euler 函数，L o g Log 为 Pólya 对数．

由于证明较复杂，读者可参考 Flajolet 的论文 The Cycle Construction 或 Analytic Combinatorics 的附录．

### 有限制的构造

对于上述所有构造，我们都没有限制其「组成部分」的个数，若在 S E Q SEQ 的下标给一个作用于整数的谓词用于约束其组成部分，如

S E Q=𝑘⁡(B),S E Q≥𝑘⁡(B),S E Q 1..𝑘⁡(B)SEQ=k⁡(B),SEQ≥k⁡(B),SEQ 1..k⁡(B)

其中 S E Q=𝑘⁡(B)SEQ=k⁡(B) 也常简写为 S E Q 𝑘⁡(B)SEQ k⁡(B)，S E Q 1..𝑘⁡(B)SEQ 1..k⁡(B) 表示在区间 [1..𝑘][1..k] 上．

令 𝔎 K 为任意上述 S E Q,P S E T,M S E T,C Y C SEQ,PSET,MSET,CYC 之一，以及

A=𝔎 𝑘(B)A=K k(B)

即我们需要对于 𝛼 ∈A α∈A 有

𝛼={(𝛽 1,𝛽 2,…,𝛽 𝑘)∣𝛽∈B}α={(β 1,β 2,…,β k)∣β∈B}

设 𝜒 χ 函数作用于组合对象上为其组成部分的个数，也就是要令 𝜒(𝛼) =𝑘 χ(α)=k，不妨增加一元来「跟踪」组成部分的个数．

令

𝐴 𝑛,𝑘=c a r d⁡{𝛼∈A∣|𝛼|=𝑛,𝜒(𝛼)=𝑘}A n,k=card⁡{α∈A∣|α|=n,χ(α)=k}

那么

𝐴(𝑧,𝑢)=∑𝑛,𝑘 𝐴 𝑛,𝑘 𝑢 𝑘 𝑧 𝑛=∑𝛼∈A 𝑧|𝛼|𝑢 𝜒(𝛼)A(z,u)=∑n,k A n,k u k z n=∑α∈A z|α|u χ(α)

然后我们只要提取出 𝑢 𝑘 u k 的系数即可获得对应表达式，例如 A =S E Q 𝑘⁡(B)A=SEQ k⁡(B) 可直接导出

𝐴(𝑧,𝑢)=∑𝑘≥0 𝑢 𝑘 𝐵(𝑧)𝑘=1 1−𝑢 𝐵(𝑧)⟹𝐴(𝑧)=𝐵(𝑧)𝑘 A(z,u)=∑k≥0 u k B(z)k=1 1−u B(z)⟹A(z)=B(z)k

显然也有

A=S E Q≥𝑘⁡(B)⟹𝐴(𝑧)=𝐵(𝑧)𝑘 1−𝐵(𝑧)A=SEQ≥k⁡(B)⟹A(z)=B(z)k 1−B(z)

而对于 M S E T 𝑘⁡(B)MSET k⁡(B) 和 P S E T 𝑘⁡(B)PSET k⁡(B) 已经有

𝐴(𝑧,𝑢)=∏𝑛(1−𝑢 𝑧 𝑛)−𝑏 𝑛⟹𝐴(𝑧)=[𝑢 𝑘]e x p⁡(𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+𝑢 3 3 𝐵(𝑧 3)+⋯)A(z,u)=∏n(1−u z n)−b n⟹A(z)=[u k]exp⁡(u 1 B(z)+u 2 2 B(z 2)+u 3 3 B(z 3)+⋯)

和

𝐴(𝑧,𝑢)=∏𝑛(1+𝑢 𝑧 𝑛)𝑏 𝑛⟹𝐴(𝑧)=[𝑢 𝑘]e x p⁡(𝑢 1 𝐵(𝑧)−𝑢 2 2 𝐵(𝑧 2)+𝑢 3 3 𝐵(𝑧 3)−⋯)A(z,u)=∏n(1+u z n)b n⟹A(z)=[u k]exp⁡(u 1 B(z)−u 2 2 B(z 2)+u 3 3 B(z 3)−⋯)

对于 C Y C 𝑘⁡(B)CYC k⁡(B) 同理．

使用上式计算 M S E T 3⁡(B)MSET 3⁡(B) 和 M S E T 4⁡(B)MSET 4⁡(B) 对应 OGF

尝试计算 A =M S E T 3⁡(B)A=MSET 3⁡(B) 为

[𝑢 3]𝐴(𝑧,𝑢)=1 0!([𝑢 3]1)+1 1!([𝑢 3](𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+𝑢 3 3 𝐵(𝑧 3)+⋯))+1 2!([𝑢 3](𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+⋯)2)+1 3!([𝑢 3](𝑢 1 𝐵(𝑧)+⋯)3)=𝐵(𝑧)3 6+𝐵(𝑧)𝐵(𝑧 2)2+𝐵(𝑧)3 3[u 3]A(z,u)=1 0!([u 3]1)+1 1!([u 3](u 1 B(z)+u 2 2 B(z 2)+u 3 3 B(z 3)+⋯))+1 2!([u 3](u 1 B(z)+u 2 2 B(z 2)+⋯)2)+1 3!([u 3](u 1 B(z)+⋯)3)=B(z)3 6+B(z)B(z 2)2+B(z)3 3

尝试计算 A =M S E T 4⁡(B)A=MSET 4⁡(B) 为

[𝑢 4]𝐴(𝑧,𝑢)=1 0!([𝑢 4]1)+1 1!([𝑢 4](𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+𝑢 3 3 𝐵(𝑧 3)+𝑢 4 4 𝐵(𝑧 4)+⋯))+1 2!([𝑢 4](𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+𝑢 3 3 𝐵(𝑧 3)+⋯)2)+1 3!([𝑢 4](𝑢 1 𝐵(𝑧)+𝑢 2 2 𝐵(𝑧 2)+⋯)3)+1 4!([𝑢 4](𝑢 1 𝐵(𝑧)+⋯)4)=𝐵(𝑧 4)4+1 2!(𝐵(𝑧 2)2 4+2 𝐵(𝑧)𝐵(𝑧 3)3)+1 3!(3 𝐵(𝑧)2 𝐵(𝑧 2)2)+𝐵(𝑧)4 4!=𝐵(𝑧)4 2 4+𝐵(𝑧)2 𝐵(𝑧 2)4+𝐵(𝑧)𝐵(𝑧 3)3+𝐵(𝑧 2)2 8+𝐵(𝑧 4)4[u 4]A(z,u)=1 0!([u 4]1)+1 1!([u 4](u 1 B(z)+u 2 2 B(z 2)+u 3 3 B(z 3)+u 4 4 B(z 4)+⋯))+1 2!([u 4](u 1 B(z)+u 2 2 B(z 2)+u 3 3 B(z 3)+⋯)2)+1 3!([u 4](u 1 B(z)+u 2 2 B(z 2)+⋯)3)+1 4!([u 4](u 1 B(z)+⋯)4)=B(z 4)4+1 2!(B(z 2)2 4+2 B(z)B(z 3)3)+1 3!(3 B(z)2 B(z 2)2)+B(z)4 4!=B(z)4 24+B(z)2 B(z 2)4+B(z)B(z 3)3+B(z 2)2 8+B(z 4)4

我们发现 A =𝔎 𝑘(B)A=K k(B) 中 𝐴(𝑧)A(z) 是关于 𝐵(𝑧),𝐵(𝑧 2),…,𝐵(𝑧 𝑘)B(z),B(z 2),…,B(z k) 的一个表达式．

需要注意的是对于有限制的构造 𝔎 𝑘(B)K k(B) 并没有要求 B 0 =∅B 0=∅．

常用有限制的构造
P S E T 2⁡(A):𝐴(𝑧)2 2−𝐴(𝑧 2)2 M S E T 2⁡(A):𝐴(𝑧)2 2+𝐴(𝑧 2)2 C Y C 2⁡(A):𝐴(𝑧)2 2+𝐴(𝑧 2)2 PSET 2⁡(A):A(z)2 2−A(z 2)2 MSET 2⁡(A):A(z)2 2+A(z 2)2 CYC 2⁡(A):A(z)2 2+A(z 2)2 P S E T 3⁡(A):𝐴(𝑧)3 6−𝐴(𝑧)𝐴(𝑧 2)2+𝐴(𝑧 3)3 M S E T 3⁡(A):𝐴(𝑧)3 6+𝐴(𝑧)𝐴(𝑧 2)2+𝐴(𝑧 3)3 C Y C 3⁡(A):𝐴(𝑧)3 3+2 𝐴(𝑧 3)3 PSET 3⁡(A):A(z)3 6−A(z)A(z 2)2+A(z 3)3 MSET 3⁡(A):A(z)3 6+A(z)A(z 2)2+A(z 3)3 CYC 3⁡(A):A(z)3 3+2 A(z 3)3 P S E T 4⁡(A):𝐴(𝑧)4 2 4−𝐴(𝑧)2 𝐴(𝑧 2)4+𝐴(𝑧)𝐴(𝑧 3)3+𝐴(𝑧 2)2 8−𝐴(𝑧 4)4 M S E T 4⁡(A):𝐴(𝑧)4 2 4+𝐴(𝑧)2 𝐴(𝑧 2)4+𝐴(𝑧)𝐴(𝑧 3)3+𝐴(𝑧 2)2 8+𝐴(𝑧 4)4 C Y C 4⁡(A):𝐴(𝑧)4 4+𝐴(𝑧 2)2 4+𝐴(𝑧 4)2 PSET 4⁡(A):A(z)4 24−A(z)2 A(z 2)4+A(z)A(z 3)3+A(z 2)2 8−A(z 4)4 MSET 4⁡(A):A(z)4 24+A(z)2 A(z 2)4+A(z)A(z 3)3+A(z 2)2 8+A(z 4)4 CYC 4⁡(A):A(z)4 4+A(z 2)2 4+A(z 4)2

上面的计算方法虽然有效但比较麻烦，读者可阅读 WolframMathWorld 网站的 Pólya Enumeration Theorem 和 Cycle Index 等相关资料，后者 Cycle Index 在 OEIS 的生成函数表达式中也经常出现．

例题 LOJ 6538. 烷基计数 加强版 加强版

题意：求出 𝑛 n 个节点的有根且根节点度数不超过 3 3，其余节点度数不超过 4 4 的无序树的个数对 9 9 8 2 4 4 3 5 3 998244353 取模的值．约定 1 ≤𝑛 ≤1 0 5 1≤n≤10 5．

解：设组合类为 T T 那么

T={∙}×M S E T 0,1,2,3⁡(T)T={∙}×MSET 0,1,2,3⁡(T)

或令组合类 ˆ T =T +{𝜖}T^=T+{ϵ} 那么

ˆ T={𝜖}+{∙}×M S E T 3⁡(ˆ T)T^={ϵ}+{∙}×MSET 3⁡(T^)

可得到相同的结果．

## 参考文献

- Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics.

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：c-forrest, Great-designer, hly1204, myeeye, shuzhouliu, Tiphereth-A
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用