符号化方法

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

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

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

无标号体系

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

$$A(z)=\sum _{\alpha \in \mathcal{A}}{z}^{|\alpha |}=\sum _{n\ge 0}{a}_n{z}^n$$

我们约定使用同一组的字母表示同一个类对应的生成函数等，例如用 $a_n$ 表示 $[z^n]A(z)$ 即 $A(z)$ 中 $z^n$ 的系数，用 ${\mathcal{A}}_n$ 表示 $\mathcal{A}$ 中大小函数为 $n$ 的对象的集合（所以 $a_n=\mathrm{card}({\mathcal{A}}_n)$ 其中 $\mathrm{card}$ 为基数（cardinality））。

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

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

• 记 $ϵ$ 为中性对象（neutral object）和 $\mathcal{E}=\{ϵ\}$ 为中性类（neutral class），中性对象的大小为 $0$，中性类的 OGF 为 $E(z)=1$。
• 记 $\circ$ 或 $\bullet$ 为原子对象（atom object）和 ${\mathcal{Z}}_{\circ }=\{\circ \}$ 或 ${\mathcal{Z}}_{\bullet }=\{\bullet \}$ 或简写为 $\mathcal{Z}$ 为原子类（atom class），原子对象的大小为 $1$，原子类的 OGF 为 $Z(z)=z$。

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

我们有

$$\mathcal{A}\cong \mathcal{E}\times \mathcal{A}\cong \mathcal{A}\times \mathcal{E}$$

其中 $\times$ 为二元运算，表示集合的笛卡尔积。

集合的（不相交）并构造

对于类 $\mathcal{A}$ 和 $\mathcal{B}$ 的并记为

$$\mathcal{A}+\mathcal{B}=({\mathcal{E}}_1\times \mathcal{A})+({\mathcal{E}}_2\times \mathcal{B})$$

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

对应 OGF 为

$$A(z)+B(z)$$

考虑

$$A(z)+B(z)=\sum _{\alpha \in \mathcal{A}}{z}^{|\alpha |}+\sum _{\beta \in \mathcal{B}}{z}^{|\beta |}=\sum _{n\ge 0}(a_n+b_n)z^n$$

对应形式幂级数的加法。

集合的笛卡尔积构造

对于类 $\mathcal{A}$ 和 $\mathcal{B}$ 的笛卡尔积记为

$$\mathcal{A}\times \mathcal{B}=\left\{(\alpha ,\beta )\mid \alpha \in \mathcal{A},\beta \in \mathcal{B}\right\}$$

对应 OGF 为

$$A(z)\cdot B(z)$$

我们定义 $(\alpha ,\beta )$ 的大小为其组成部分的大小之和，那么显然也有

$$\gamma =({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)⟹|\gamma |=|{\alpha }_1|+|{\alpha }_2|+\cdots +|{\alpha }_n|$$

所以

$$A(z)\cdot B(z)=\left(\sum _{\alpha \in \mathcal{A}}{z}^{|\alpha |}\right)\left(\sum _{\beta \in \mathcal{B}}{z}^{|\beta |}\right)=\sum _{(\alpha ,\beta )\in (\mathcal{A}\times \mathcal{B})}{z}^{|\alpha |+|\beta |}=\sum _{n\ge 0}\sum _{i+j=n}{a}_i{b}_j{z}^n$$

对应形式幂级数的乘法。

集合的 Sequence 构造

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

例

$$\begin{array}{rl}\mathrm{SEQ}(\{a\})& =\{ϵ\}+\{a\}+\{(a,a)\}+\{(a,a,a)\}+\cdots \\ \mathrm{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)\}\\ & +\cdots \end{array}$$

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

我们定义

$$\mathrm{SEQ}(\mathcal{A})=\mathcal{E}+\mathcal{A}+(\mathcal{A}\times \mathcal{A})+(\mathcal{A}\times \mathcal{A}\times \mathcal{A})+\cdots$$

且要求 ${\mathcal{A}}_0=\varnothing$，也就是 $\mathcal{A}$ 中没有大小为 $0$ 的对象。

对应 OGF 为

$$Q(A(z))=1+A(z)+A(z{)}^2+A(z{)}^3+\cdots =\frac{1}{1-A(z)}$$

其中 $Q$ 为 Pólya 准逆（quasi-inversion）。

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

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

$$\mathcal{T}=\{\bullet \}\times \mathrm{SEQ}(\mathcal{T})$$

对应 OGF 为

$$T(z)=\frac{z}{1-T(z)}$$

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

集合的 Multiset 构造

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

例

$$\begin{array}{rl}\mathrm{MSET}(\{a\})& =\{ϵ\}+\{a\}+\{(a,a)\}+\{(a,a,a)\}+\cdots \\ \mathrm{MSET}(\{a,b\})& =\{ϵ\}+\{a\}+\{(a,a)\}+\{(a,a,a)\}+\cdots \\ & +\{b\}+\{(a,b)\}+\{(a,a,b)\}+\cdots \\ & +\{(b,b)\}+\{(a,b,b)\}+\{(a,a,b,b)\}+\cdots \\ & +\cdots \end{array}$$

注意到 $\{(b,a)\},\{(a,b,a)\}$ 在 $\mathrm{SEQ}(\{a,b\})$ 中出现，但在 $\mathrm{MSET}(\{a,b\})$ 没有出现，可以认为 Multiset 生成了无序的组合。

我们定义其递推式为

$$\mathrm{MSET}(\{{\alpha }_0,{\alpha }_1,\dots ,{\alpha }_n\})=\mathrm{MSET}(\{{\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{n-1}\})\times \mathrm{SEQ}(\{{\alpha }_n\})$$

即

$$\mathrm{MSET}(\mathcal{A})=\prod _{\alpha \in \mathcal{A}}\mathrm{SEQ}(\{\alpha \})$$

且要求 ${\mathcal{A}}_0=\varnothing$。或者也可以给出等价的

$$\mathrm{MSET}(\mathcal{A})=\mathrm{SEQ}(\mathcal{A})/\mathbf{R}$$

其中 $\mathbf{R}$ 为等价关系，我们说 $({\alpha }_1,\dots ,{\alpha }_n)\mathbf{R}({\beta }_1,\dots ,{\beta }_n)$ 当且仅当存在任一置换 $\sigma$ 对于所有 $j$ 满足 ${\beta }_j={\alpha }_{\sigma (j)}$。

对应 OGF 为

$$\mathrm{Exp}(A(z))=\prod _{\alpha \in \mathcal{A}}{\left(1-z^{|\alpha |}\right)}^{-1}=\prod _{n\ge 1}{\left(1-z^n\right)}^{-a_n}$$

注意到

$$\ln (1+z)=\frac{z}{1}-\frac{z^2}{2}+\frac{z^3}{3}-\cdots =\sum _{n\ge 1}\frac{(-1{)}^{n-1}{z}^n}{n}$$

且 $A(z)=\exp (\ln (A(z)))$ 所以

$$\begin{array}{rl}\mathrm{Exp}(A(z))& =\exp \left(\sum _{n\ge 1}-a_n\cdot \ln \left(1-z^n\right)\right)\\ & =\exp \left(\sum _{n\ge 1}-a_n\cdot \sum _{m\ge 1}\frac{-z^{nm}}{m}\right)\\ & =\exp \left(\frac{A(z)}{1}+\frac{A(z^2)}{2}+\frac{A(z^3)}{3}+\cdots \right)\end{array}$$

其中 $\mathrm{Exp}$ 为 Pólya 指数，也被称为 Euler 变换。

例题 LOJ 6268. 分拆数

题意：令 $f(n)$ 表示将 $n$ 进行分拆的方案数，求 $f(1),f(2),\dots ,f(10^5)$ 对 $998244353$ 取模的值。

解：设全体正整数类为 $\mathcal{I}$，那么 $\mathcal{I}={\mathrm{SEQ}}_{\ge 1}(\mathcal{Z})=\mathcal{Z}\times \mathrm{SEQ}(\mathcal{Z})$（下标 $\ge 1$ 为有限制的构造，见后文）。所求即

$$\mathrm{MSET}(\mathcal{I})$$

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

例题 洛谷 P4389 付公主的背包

题意：给出 $n$ 种体积分别为 $v_1,\dots ,v_n$ 的商品和正整数 $m$，求体积为 $1,2,\dots ,m$ 的背包装满的方案数（商品数量不限，有同体积的不同种商品）对 $998244353$ 取模的值。约定 $1\le n,m\le 10^5$ 且 $1\le v_i\le m$。

解：设商品的组合类为 $\mathcal{A}$，所求即 $\mathrm{MSET}(\mathcal{A})$ 对应 OGF 的系数。

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

题意：求出 $n$ 个节点的无标号无根树的个数对 $998244353$ 取模的值。约定 $1\le n\le 2\times 10^5$。

解：设无标号有根树的组合类为 $\mathcal{T}$，那么

$$\mathcal{T}=\{\bullet \}\times \mathrm{MSET}(\mathcal{T})$$

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

$$T(z)-\frac{1}{2}{T}^2(z)+\frac{1}{2}T(z^2)$$

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

集合的 Powerset 构造

Powerset 构造生成了所有子集。

例

$$\begin{array}{rl}\mathrm{PSET}(\{a\})& =\{ϵ\}+\{a\}\\ \mathrm{PSET}(\{a,b\})& =\{ϵ\}+\{a\}+\{b\}+\{(a,b)\}\\ \mathrm{PSET}(\{a,b,c\})& =\{ϵ\}+\{a\}+\{b\}+\{(a,b)\}+\{c\}+\{(a,c)\}+\{(b,c)\}+\{(a,b,c)\}\end{array}$$

我们定义其递推式为

$$\mathrm{PSET}(\{{\alpha }_0,{\alpha }_1,\dots ,{\alpha }_n\})=\mathrm{PSET}(\{{\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{n-1}\})\times (\{ϵ\}+\{{\alpha }_n\})$$

即

$$\mathrm{PSET}(\mathcal{A})\cong \prod _{\alpha \in \mathcal{A}}\left(\{ϵ\}+\{\alpha \}\right)$$

且要求 ${\mathcal{A}}_0=\varnothing$。

对应 OGF 为

$$\begin{array}{rl}\overline{\mathrm{Exp}}(A(z))& =\prod _{\alpha \in \mathcal{A}}\left(1+z^{|\alpha |}\right)=\prod _{n\ge 1}{\left(1+z^n\right)}^{a_n}\\ & =\exp \left(\sum _{n\ge 1}{a}_n\cdot \ln \left(1+z^n\right)\right)\\ & =\exp \left(\sum _{n\ge 1}{a}_n\cdot \sum _{m\ge 1}\frac{(-1{)}^{m-1}{z}^{nm}}{m}\right)\\ & =\exp \left(\frac{A(z)}{1}-\frac{A(z^2)}{2}+\frac{A(z^3)}{3}-\cdots \right)\end{array}$$

其中 $\overline{\mathrm{Exp}}$ 为 Pólya 指数·改。

容易发现 $\mathrm{PSET}(\mathcal{A})\subset \mathrm{MSET}(\mathcal{A})$。

集合的 Cycle 构造

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

我们定义为

$$\mathrm{CYC}(\mathcal{A})=\left(\mathrm{SEQ}(\mathcal{A})\setminus \{ϵ\}\right)/\mathbf{S}$$

其中 $\mathbf{S}$ 为等价关系，我们说 $({\alpha }_1,\dots ,{\alpha }_n)\mathbf{S}({\beta }_1,\dots ,{\beta }_n)$ 当且仅当存在任一循环移位 $\tau$ 对于所有 $j$ 都满足 ${\beta }_j={\alpha }_{\tau (j)}$。

例

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

$$\mathrm{CYC}(\{\text{a},\text{b}\}{)}_3=\{\text{aaa}\}+\{\text{aab}\}+\{\text{abb}\}+\{\text{bbb}\}$$

其中 $\text{aab}\mathbf{S}\text{baa}\mathbf{S}\text{aba}$ 只保留其一，同样的 $\text{abb}\mathbf{S}\text{bab}\mathbf{S}\text{bba}$ 只保留其一。

$$\mathrm{CYC}(\{\text{a},\text{b}\}{)}_4=\{\text{aaaa}\}+\{\text{aaab}\}+\{\text{aabb}\}+\{\text{abbb}\}+\{\text{bbbb}\}+\{\text{abab}\}$$

其中 $\text{aaab}\mathbf{S}\text{baaa}\mathbf{S}\text{abaa}\mathbf{S}\text{aaba}$，$\text{aabb}\mathbf{S}\text{baab}\mathbf{S}\text{bbaa}\mathbf{S}\text{abba}$，$\text{abbb}\mathbf{S}\text{babb}\mathbf{S}\text{bbab}\mathbf{S}\text{bbba}$ 和 $\text{abab}\mathbf{S}\text{baba}$。

对应 OGF 为

$$\mathrm{Log}(A(z))=\sum _{n\ge 1}\frac{\phi (n)}{n}\ln \frac{1}{1-A(z^n)}$$

其中 $\phi$ 为 Euler 函数，$\mathrm{Log}$ 为 Pólya 对数。

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

有限制的构造

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

$${\mathrm{SEQ}}_{=k}(\mathcal{B}),{\mathrm{SEQ}}_{\ge k}(\mathcal{B}),{\mathrm{SEQ}}_{\mathrm{1..}k}(\mathcal{B})$$

其中 ${\mathrm{SEQ}}_{=k}(\mathcal{B})$ 也常简写为 ${\mathrm{SEQ}}_k(\mathcal{B})$，${\mathrm{SEQ}}_{\mathrm{1..}k}(\mathcal{B})$ 表示在区间 $[\mathrm{1..}k]$ 上。

令 $\mathfrak{K}$ 为任意上述 $\mathrm{SEQ},\mathrm{PSET},\mathrm{MSET},\mathrm{CYC}$ 之一，以及

$$\mathcal{A}={\mathfrak{K}}_k(\mathcal{B})$$

即我们需要对于 $\alpha \in \mathcal{A}$ 有

$$\alpha =\{({\beta }_1,{\beta }_2,\dots ,{\beta }_k)\mid \beta \in \mathcal{B}\}$$

设 $\chi$ 函数作用于组合对象上为其组成部分的个数，也就是要令 $\chi (\alpha )=k$，不妨增加一元来「跟踪」组成部分的个数。

令

$$A_{n,k}=\mathrm{card}\left\{\alpha \in \mathcal{A}\mid |\alpha |=n,\chi (\alpha )=k\right\}$$

那么

$$A(z,u)=\sum _{n,k}{A}_{n,k}{u}^k{z}^n=\sum _{\alpha \in \mathcal{A}}{z}^{|\alpha |}{u}^{\chi (\alpha )}$$

然后我们只要提取出 $u^k$ 的系数即可获得对应表达式，例如 $\mathcal{A}={\mathrm{SEQ}}_k(\mathcal{B})$ 可直接导出

$$\begin{array}{rl}& A(z,u)=\sum _{k\ge 0}{u}^{k}B(z{)}^k=\frac{1}{1-uB(z)}\\ ⟹& A(z)=B(z{)}^k\end{array}$$

显然也有

$$\mathcal{A}={\mathrm{SEQ}}_{\ge k}(\mathcal{B})⟹A(z)=\frac{B(z{)}^k}{1-B(z)}$$

而对于 ${\mathrm{MSET}}_k(\mathcal{B})$ 和 ${\mathrm{PSET}}_k(\mathcal{B})$ 已经有

$$\begin{array}{rl}& A(z,u)=\prod _n{\left(1-u{z}^n\right)}^{-b_n}\\ ⟹& A(z)=[u^k]\exp \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots \right)\end{array}$$

和

$$\begin{array}{rl}& A(z,u)=\prod _n{\left(1+u{z}^n\right)}^{b_n}\\ ⟹& A(z)=[u^k]\exp \left(\frac{u}{1}B(z)-\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)-\cdots \right)\end{array}$$

对于 ${\mathrm{CYC}}_k(\mathcal{B})$ 同理。

使用上式计算 ${\mathrm{MSET}}_3(\mathcal{B})$ 和 ${\mathrm{MSET}}_4(\mathcal{B})$ 对应 OGF

尝试计算 $\mathcal{A}={\mathrm{MSET}}_3(\mathcal{B})$ 为

$$\begin{array}{rl}[u^3]A(z,u)& =\frac{1}{0!}\left([u^3]1\right)+\frac{1}{1!}\left([u^3]\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots \right)\right)\\ & +\frac{1}{2!}\left([u^3]{\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)}^2\right)\\ & +\frac{1}{3!}\left([u^3]{\left(\frac{u}{1}B(z)+\cdots \right)}^3\right)\\ & =\frac{B(z{)}^3}{6}+\frac{B(z)B(z^2)}{2}+\frac{B(z{)}^3}{3}\end{array}$$

尝试计算 $\mathcal{A}={\mathrm{MSET}}_4(\mathcal{B})$ 为

$$\begin{array}{rl}[u^4]A(z,u)& =\frac{1}{0!}\left([u^4]1\right)+\frac{1}{1!}\left([u^4]\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\frac{u^4}{4}B(z^4)+\cdots \right)\right)\\ & +\frac{1}{2!}\left([u^4]{\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots \right)}^2\right)\\ & +\frac{1}{3!}\left([u^4]{\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)}^3\right)\\ & +\frac{1}{4!}\left([u^4]{\left(\frac{u}{1}B(z)+\cdots \right)}^4\right)\\ & =\frac{B(z^4)}{4}+\frac{1}{2!}\left(\frac{B(z^2{)}^2}{4}+\frac{2B(z)B(z^3)}{3}\right)+\frac{1}{3!}\left(\frac{3B(z{)}^{2}B(z^2)}{2}\right)+\frac{B(z{)}^4}{4!}\\ & =\frac{B(z{)}^4}{24}+\frac{B(z{)}^{2}B(z^2)}{4}+\frac{B(z)B(z^3)}{3}+\frac{B(z^2{)}^2}{8}+\frac{B(z^4)}{4}\end{array}$$

我们发现 $\mathcal{A}={\mathfrak{K}}_k(\mathcal{B})$ 中 $A(z)$ 是关于 $B(z),B(z^2),\dots ,B(z^k)$ 的一个表达式。

需要注意的是对于有限制的构造 ${\mathfrak{K}}_k(\mathcal{B})$ 并没有要求 ${\mathcal{B}}_0=\varnothing$。

常用有限制的构造

$$\begin{array}{rl}{\mathrm{PSET}}_2(\mathcal{A})& :\frac{A(z{)}^2}{2}-\frac{A(z^2)}{2}\\ {\mathrm{MSET}}_2(\mathcal{A})& :\frac{A(z{)}^2}{2}+\frac{A(z^2)}{2}\\ {\mathrm{CYC}}_2(\mathcal{A})& :\frac{A(z{)}^2}{2}+\frac{A(z^2)}{2}\end{array}$$ $$\begin{array}{rl}{\mathrm{PSET}}_3(\mathcal{A})& :\frac{A(z{)}^3}{6}-\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\ {\mathrm{MSET}}_3(\mathcal{A})& :\frac{A(z{)}^3}{6}+\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\ {\mathrm{CYC}}_3(\mathcal{A})& :\frac{A(z{)}^3}{3}+\frac{2A(z^3)}{3}\end{array}$$ $$\begin{array}{rl}{\mathrm{PSET}}_4(\mathcal{A})& :\frac{A(z{)}^4}{24}-\frac{A(z{)}^{2}A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2{)}^2}{8}-\frac{A(z^4)}{4}\\ {\mathrm{MSET}}_4(\mathcal{A})& :\frac{A(z{)}^4}{24}+\frac{A(z{)}^{2}A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2{)}^2}{8}+\frac{A(z^4)}{4}\\ {\mathrm{CYC}}_4(\mathcal{A})& :\frac{A(z{)}^4}{4}+\frac{A(z^2{)}^2}{4}+\frac{A(z^4)}{2}\end{array}$$

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

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

题意：求出 $n$ 个节点的有根且根节点度数不超过 $3$，其余节点度数不超过 $4$ 的无序树的个数对 $998244353$ 取模的值。约定 $1\le n\le 10^5$。

解：设组合类为 $\mathcal{T}$ 那么

$$\mathcal{T}=\{\bullet \}\times {\mathrm{MSET}}_{0,1,2,3}(\mathcal{T})$$

或令组合类 $\hat{\mathcal{T}}=\mathcal{T}+\{ϵ\}$ 那么

$$\hat{\mathcal{T}}=\{ϵ\}+\{\bullet \}\times {\mathrm{MSET}}_3(\hat{\mathcal{T}})$$

可得到相同的结果。

参考文献

• Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics.