本地源文件：docs/math__poly__symbolic-method.md

符号化方法

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

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

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

无标号体系

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

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

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

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

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

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

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

我们有

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

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

集合的（不相交）并构造

对于类 AA 和 BB 的并记为

A+B=(E1×A)+(E2×B)A+B=(E1×A)+(E2×B)

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

对应 OGF 为

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

考虑

𝐴(𝑧)+𝐵(𝑧)=∑𝛼∈A𝑧|𝛼|+∑𝛽∈B𝑧|𝛽|=∑𝑛≥0(𝑎𝑛+𝑏𝑛)𝑧𝑛A(z)+B(z)=∑α∈Az|α|+∑β∈Bz|β|=∑n≥0(an+bn)zn

对应形式幂级数的加法．

集合的笛卡尔积构造

对于类 AA 和 BB 的笛卡尔积记为

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)=(∑α∈Az|α|)(∑β∈Bz|β|)=∑(α,β)∈(A×B)z|α|+|β|=∑n≥0∑i+j=naibjzn

对应形式幂级数的乘法．

集合的 Sequence 构造

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

例 SEQ⁡({𝑎})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯SEQ⁡({𝑎,𝑏})={𝜖}+{𝑎,𝑏}+{(𝑎,𝑏)}+{(𝑏,𝑎)}+{(𝑎,𝑎)}+{(𝑏,𝑏)}+{(𝑎,𝑏,𝑎)}+{(𝑎,𝑏,𝑏)}+{(𝑎,𝑎,𝑏)}+{(𝑏,𝑏,𝑎)}+{(𝑏,𝑎,𝑏)}+{(𝑏,𝑏,𝑏)}+{(𝑎,𝑎,𝑎)}+{(𝑏,𝑎,𝑎)}+⋯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 构造生成了有序的组合．

我们定义

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

且要求 A0 =∅A0=∅，也就是 AA 中没有大小为 00 的对象．

对应 OGF 为

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

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

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

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

T={∙}×SEQ⁡(T)T={∙}×SEQ⁡(T)

对应 OGF 为

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

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

集合的 Multiset 构造

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

例 MSET⁡({𝑎})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯MSET⁡({𝑎,𝑏})={𝜖}+{𝑎}+{(𝑎,𝑎)}+{(𝑎,𝑎,𝑎)}+⋯+{𝑏}+{(𝑎,𝑏)}+{(𝑎,𝑎,𝑏)}+⋯+{(𝑏,𝑏)}+{(𝑎,𝑏,𝑏)}+{(𝑎,𝑎,𝑏,𝑏)}+⋯+⋯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)} 在 SEQ⁡({𝑎,𝑏})SEQ⁡({a,b}) 中出现，但在 MSET⁡({𝑎,𝑏})MSET⁡({a,b}) 没有出现，可以认为 Multiset 生成了无序的组合．

我们定义其递推式为

MSET⁡({𝛼0,𝛼1,…,𝛼𝑛})=MSET⁡({𝛼0,𝛼1,…,𝛼𝑛−1})×SEQ⁡({𝛼𝑛})MSET⁡({α0,α1,…,αn})=MSET⁡({α0,α1,…,αn−1})×SEQ⁡({αn})

即

MSET⁡(A)=∏𝛼∈ASEQ⁡({𝛼})MSET⁡(A)=∏α∈ASEQ⁡({α})

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

MSET⁡(A)=SEQ⁡(A)/𝐑MSET⁡(A)=SEQ⁡(A)/R

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

对应 OGF 为

Exp⁡(𝐴(𝑧))=∏𝛼∈A(1−𝑧|𝛼|)−1=∏𝑛≥1(1−𝑧𝑛)−𝑎𝑛Exp⁡(A(z))=∏α∈A(1−z|α|)−1=∏n≥1(1−zn)−an

注意到

ln⁡(1+𝑧)=𝑧1−𝑧22+𝑧33−⋯=∑𝑛≥1(−1)𝑛−1𝑧𝑛𝑛ln⁡(1+z)=z1−z22+z33−⋯=∑n≥1(−1)n−1znn

且 𝐴(𝑧) =exp⁡(ln⁡(𝐴(𝑧)))A(z)=exp⁡(ln⁡(A(z))) 所以

Exp⁡(𝐴(𝑧))=exp⁡(∑𝑛≥1−𝑎𝑛⋅ln⁡(1−𝑧𝑛))=exp⁡(∑𝑛≥1−𝑎𝑛⋅∑𝑚≥1−𝑧𝑛𝑚𝑚)=exp⁡(𝐴(𝑧)1+𝐴(𝑧2)2+𝐴(𝑧3)3+⋯)Exp⁡(A(z))=exp⁡(∑n≥1−an⋅ln⁡(1−zn))=exp⁡(∑n≥1−an⋅∑m≥1−znmm)=exp⁡(A(z)1+A(z2)2+A(z3)3+⋯)

其中 ExpExp 为 Pólya 指数，也被称为 Euler 变换．

例题 LOJ 6268. 分拆数

题意 ：令 𝑓(𝑛)f(n) 表示将 𝑛n 进行分拆的方案数，求 𝑓(1),𝑓(2),…,𝑓(105)f(1),f(2),…,f(105) 对 998244353998244353 取模的值．

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

MSET⁡(I)MSET⁡(I)

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

例题 洛谷 P4389 付公主的背包

题意 ：给出 𝑛n 种体积分别为 𝑣1,…,𝑣𝑛v1,…,vn 的商品和正整数 𝑚m，求体积为 1,2,…,𝑚1,2,…,m 的背包装满的方案数（商品数量不限，有同体积的不同种商品）对 998244353998244353 取模的值．约定 1 ≤𝑛,𝑚 ≤1051≤n,m≤105 且 1 ≤𝑣𝑖 ≤𝑚1≤vi≤m．

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

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

题意 ：求出 𝑛n 个节点的无标号无根树的个数对 998244353998244353 取模的值．约定 1 ≤𝑛 ≤2 ×1051≤n≤2×105．

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

T={∙}×MSET⁡(T)T={∙}×MSET⁡(T)

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

𝑇(𝑧)−12𝑇2(𝑧)+12𝑇(𝑧2)T(z)−12T2(z)+12T(z2)

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

集合的 Powerset 构造

Powerset 构造生成了所有子集．

例 PSET⁡({𝑎})={𝜖}+{𝑎}PSET⁡({𝑎,𝑏})={𝜖}+{𝑎}+{𝑏}+{(𝑎,𝑏)}PSET⁡({𝑎,𝑏,𝑐})={𝜖}+{𝑎}+{𝑏}+{(𝑎,𝑏)}+{𝑐}+{(𝑎,𝑐)}+{(𝑏,𝑐)}+{(𝑎,𝑏,𝑐)}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)}

我们定义其递推式为

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

即

PSET⁡(A)≅∏𝛼∈A({𝜖}+{𝛼})PSET⁡(A)≅∏α∈A({ϵ}+{α})

且要求 A0 =∅A0=∅．

对应 OGF 为

―――Exp(𝐴(𝑧))=∏𝛼∈A(1+𝑧|𝛼|)=∏𝑛≥1(1+𝑧𝑛)𝑎𝑛=exp⁡(∑𝑛≥1𝑎𝑛⋅ln⁡(1+𝑧𝑛))=exp⁡(∑𝑛≥1𝑎𝑛⋅∑𝑚≥1(−1)𝑚−1𝑧𝑛𝑚𝑚)=exp⁡(𝐴(𝑧)1−𝐴(𝑧2)2+𝐴(𝑧3)3−⋯)Exp―(A(z))=∏α∈A(1+z|α|)=∏n≥1(1+zn)an=exp⁡(∑n≥1an⋅ln⁡(1+zn))=exp⁡(∑n≥1an⋅∑m≥1(−1)m−1znmm)=exp⁡(A(z)1−A(z2)2+A(z3)3−⋯)

其中 ―――ExpExp― 为 Pólya 指数·改．

容易发现 PSET⁡(A) ⊂MSET⁡(A)PSET⁡(A)⊂MSET⁡(A)．

集合的 Cycle 构造

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

我们定义为

CYC⁡(A)=(SEQ⁡(A)∖{𝜖})/𝐒CYC⁡(A)=(SEQ⁡(A)∖{ϵ})/S

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

例

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

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

其中 𝚊𝚊𝚋𝐒𝚋𝚊𝚊𝐒𝚊𝚋𝚊aabSbaaSaba 只保留其一，同样的 𝚊𝚋𝚋𝐒𝚋𝚊𝚋𝐒𝚋𝚋𝚊abbSbabSbba 只保留其一．

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

其中 𝚊𝚊𝚊𝚋𝐒𝚋𝚊𝚊𝚊𝐒𝚊𝚋𝚊𝚊𝐒𝚊𝚊𝚋𝚊aaabSbaaaSabaaSaaba，𝚊𝚊𝚋𝚋𝐒𝚋𝚊𝚊𝚋𝐒𝚋𝚋𝚊𝚊𝐒𝚊𝚋𝚋𝚊aabbSbaabSbbaaSabba，𝚊𝚋𝚋𝚋𝐒𝚋𝚊𝚋𝚋𝐒𝚋𝚋𝚊𝚋𝐒𝚋𝚋𝚋𝚊abbbSbabbSbbabSbbba 和 𝚊𝚋𝚊𝚋𝐒𝚋𝚊𝚋𝚊ababSbaba．

对应 OGF 为

Log⁡(𝐴(𝑧))=∑𝑛≥1𝜑(𝑛)𝑛ln⁡11−𝐴(𝑧𝑛)Log⁡(A(z))=∑n≥1φ(n)nln⁡11−A(zn)

其中 𝜑φ 为 Euler 函数，LogLog 为 Pólya 对数．

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

有限制的构造

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

SEQ=𝑘⁡(B),SEQ≥𝑘⁡(B),SEQ1..𝑘⁡(B)SEQ=k⁡(B),SEQ≥k⁡(B),SEQ1..k⁡(B)

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

令 𝔎K 为任意上述 SEQ,PSET,MSET,CYCSEQ,PSET,MSET,CYC 之一，以及

A=𝔎𝑘(B)A=Kk(B)

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

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

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

令

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

那么

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

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

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

显然也有

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

而对于 MSET𝑘⁡(B)MSETk⁡(B) 和 PSET𝑘⁡(B)PSETk⁡(B) 已经有

𝐴(𝑧,𝑢)=∏𝑛(1−𝑢𝑧𝑛)−𝑏𝑛⟹𝐴(𝑧)=[𝑢𝑘]exp⁡(𝑢1𝐵(𝑧)+𝑢22𝐵(𝑧2)+𝑢33𝐵(𝑧3)+⋯)A(z,u)=∏n(1−uzn)−bn⟹A(z)=[uk]exp⁡(u1B(z)+u22B(z2)+u33B(z3)+⋯)

和

𝐴(𝑧,𝑢)=∏𝑛(1+𝑢𝑧𝑛)𝑏𝑛⟹𝐴(𝑧)=[𝑢𝑘]exp⁡(𝑢1𝐵(𝑧)−𝑢22𝐵(𝑧2)+𝑢33𝐵(𝑧3)−⋯)A(z,u)=∏n(1+uzn)bn⟹A(z)=[uk]exp⁡(u1B(z)−u22B(z2)+u33B(z3)−⋯)

对于 CYC𝑘⁡(B)CYCk⁡(B) 同理．

使用上式计算 MSET3⁡(B)MSET3⁡(B) 和 MSET4⁡(B)MSET4⁡(B) 对应 OGF

尝试计算 A =MSET3⁡(B)A=MSET3⁡(B) 为

[𝑢3]𝐴(𝑧,𝑢)=10!([𝑢3]1)+11!(𝑢3+𝑢22𝐵(𝑧2)+𝑢33𝐵(𝑧3)+⋯))+12!(𝑢3+𝑢22𝐵(𝑧2)+⋯)2)+13!(𝑢3+⋯)3)=𝐵(𝑧)36+𝐵(𝑧)𝐵(𝑧2)2+𝐵(𝑧)33[u3]A(z,u)=10!([u3]1)+11!(u3+u22B(z2)+u33B(z3)+⋯))+12!(u3+u22B(z2)+⋯)2)+13!(u3+⋯)3)=B(z)36+B(z)B(z2)2+B(z)33

尝试计算 A =MSET4⁡(B)A=MSET4⁡(B) 为

[𝑢4]𝐴(𝑧,𝑢)=10!([𝑢4]1)+11!(𝑢4+𝑢22𝐵(𝑧2)+𝑢33𝐵(𝑧3)+𝑢44𝐵(𝑧4)+⋯))+12!(𝑢4+𝑢22𝐵(𝑧2)+𝑢33𝐵(𝑧3)+⋯)2)+13!(𝑢4+𝑢22𝐵(𝑧2)+⋯)3)+14!(𝑢4+⋯)4)=𝐵(𝑧4)4+12!(𝐵(𝑧2)24+2𝐵(𝑧)𝐵(𝑧3)3)+13!(3𝐵(𝑧)2𝐵(𝑧2)2)+𝐵(𝑧)44!=𝐵(𝑧)424+𝐵(𝑧)2𝐵(𝑧2)4+𝐵(𝑧)𝐵(𝑧3)3+𝐵(𝑧2)28+𝐵(𝑧4)4[u4]A(z,u)=10!([u4]1)+11!(u4+u22B(z2)+u33B(z3)+u44B(z4)+⋯))+12!(u4+u22B(z2)+u33B(z3)+⋯)2)+13!(u4+u22B(z2)+⋯)3)+14!(u4+⋯)4)=B(z4)4+12!(B(z2)24+2B(z)B(z3)3)+13!(3B(z)2B(z2)2)+B(z)44!=B(z)424+B(z)2B(z2)4+B(z)B(z3)3+B(z2)28+B(z4)4

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

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

常用有限制的构造 PSET2⁡(A):𝐴(𝑧)22−𝐴(𝑧2)2MSET2⁡(A):𝐴(𝑧)22+𝐴(𝑧2)2CYC2⁡(A):𝐴(𝑧)22+𝐴(𝑧2)2PSET2⁡(A):A(z)22−A(z2)2MSET2⁡(A):A(z)22+A(z2)2CYC2⁡(A):A(z)22+A(z2)2 PSET3⁡(A):𝐴(𝑧)36−𝐴(𝑧)𝐴(𝑧2)2+𝐴(𝑧3)3MSET3⁡(A):𝐴(𝑧)36+𝐴(𝑧)𝐴(𝑧2)2+𝐴(𝑧3)3CYC3⁡(A):𝐴(𝑧)33+2𝐴(𝑧3)3PSET3⁡(A):A(z)36−A(z)A(z2)2+A(z3)3MSET3⁡(A):A(z)36+A(z)A(z2)2+A(z3)3CYC3⁡(A):A(z)33+2A(z3)3 PSET4⁡(A):𝐴(𝑧)424−𝐴(𝑧)2𝐴(𝑧2)4+𝐴(𝑧)𝐴(𝑧3)3+𝐴(𝑧2)28−𝐴(𝑧4)4MSET4⁡(A):𝐴(𝑧)424+𝐴(𝑧)2𝐴(𝑧2)4+𝐴(𝑧)𝐴(𝑧3)3+𝐴(𝑧2)28+𝐴(𝑧4)4CYC4⁡(A):𝐴(𝑧)44+𝐴(𝑧2)24+𝐴(𝑧4)2PSET4⁡(A):A(z)424−A(z)2A(z2)4+A(z)A(z3)3+A(z2)28−A(z4)4MSET4⁡(A):A(z)424+A(z)2A(z2)4+A(z)A(z3)3+A(z2)28+A(z4)4CYC4⁡(A):A(z)44+A(z2)24+A(z4)2

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

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

题意 ：求出 𝑛n 个节点的有根且根节点度数不超过 33，其余节点度数不超过 44 的无序树的个数对 998244353998244353 取模的值．约定 1 ≤𝑛 ≤1051≤n≤105．

解 ：设组合类为 TT 那么

T={∙}×MSET0,1,2,3⁡(T)T={∙}×MSET0,1,2,3⁡(T)

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

ˆT={𝜖}+{∙}×MSET3⁡(ˆT)T^={ϵ}+{∙}×MSET3⁡(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 协议之条款下提供，附加条款亦可能应用