符號化方法
符號化方法（symbolic method）是將組合對象快速轉換成生成函數的一種方法，我們將考慮對於集合上定義的特定運算，然後導出其對應的生成函數的運算。
我們稱一個組合類（或簡稱為類）為 \((\mathcal{A},\lvert \cdot \rvert)\)，其中 \(\mathcal{A}\) 為組合對象的集合，函數 \(\lvert \cdot \rvert\) 將每一個組合對象映射為一個非負整數，一般稱為大小函數。需要注意的是這個非負整數不能是無限大的。例如對於字符集為 \(\lbrace 0,1\rbrace\) 的字符串，可以將字符串的長度設置為其大小函數；對於樹或圖可將節點的數量設置為其大小函數，注意這並非絕對，也可能將某些特定節點的大小函數設置為 \(0\) 等。
本文是基於 Analytic Combinatorics 一書第一章的簡化。
無標號體系
在無標號體系中將使用普通生成函數（OGF）。對於集合 \(\mathcal{A}\) 其對應 OGF 記為
\[
A(z)=\sum_{\alpha\in\mathcal{A}}z^{\lvert \alpha \rvert}=\sum_{n\geq 0}a_nz^n
\]
我們約定使用同一組的字母表示同一個類對應的生成函數等，例如用 \(a_n\) 表示 \(\lbrack z^n\rbrack A(z)\) 即 \(A(z)\) 中 \(z^n\) 的係數，用 \(\mathcal{A}_n\) 表示 \(\mathcal{A}\) 中大小函數為 \(n\) 的對象的集合（所以 \(a_n=\operatorname{card}(\mathcal{A}_n)\) 其中 \(\operatorname{card}\) 為基數（cardinality））。
本文將不討論可容許性（admissibility），讀者可參考文獻中的內容。
下面將引入兩種特殊的組合類和組合對象：
- 記 \(\epsilon\) 為中性對象（neutral object）和 \(\mathcal{E}=\lbrace \epsilon \rbrace\) 為中性類（neutral class），中性對象的大小為 \(0\)，中性類的 OGF 為 \(E(z)=1\)。
- 記 \(\circ\) 或 \(\bullet\) 為原子對象（atom object）和 \(\mathcal{Z}_{\circ}=\lbrace \circ\rbrace\) 或 \(\mathcal{Z}_{\bullet}=\lbrace \bullet\rbrace\) 或簡寫為 \(\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^{\lvert \alpha\rvert} + \sum _ {\beta\in\mathcal{B}}z^{\lvert \beta\rvert}=\sum_{n\geq 0}(a_n+b_n)z^n
\]
對應形式冪級數的加法。
集合的笛卡爾積構造
對於類 \(\mathcal{A}\) 和 \(\mathcal{B}\) 的笛卡爾積記為
\[
\mathcal{A}\times \mathcal{B}=\left\lbrace (\alpha, \beta)\mid \alpha \in \mathcal{A},\beta\in\mathcal{B}\right\rbrace
\]
對應 OGF 為
\[
A(z)\cdot B(z)
\]
我們定義 \((\alpha,\beta)\) 的大小為其組成部分的大小之和，那麼顯然也有
\[
\gamma =(\alpha_1,\alpha_2,\dots ,\alpha_n)\implies \lvert \gamma\rvert =\lvert \alpha_1\rvert +\lvert \alpha_2\rvert +\cdots +\lvert \alpha_n\rvert
\]
所以
\[
A(z)\cdot B(z)=\left(\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert}\right)\left(\sum _ {\beta\in\mathcal{B}}z^{\lvert \beta\rvert}\right)=\sum _ {(\alpha, \beta)\in(\mathcal{A}\times \mathcal{B})}z^{\lvert \alpha\rvert +\lvert \beta\rvert}=\sum_{n\geq 0}\sum_{i+j=n}a_ib_jz^n
\]
對應形式冪級數的乘法。
集合的 Sequence 構造
Sequence 構造生成了所有可能的組合。
例
\[
\begin{aligned}
\operatorname{SEQ}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\
\operatorname{SEQ}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a,b\rbrace +\lbrace (a,b)\rbrace + \lbrace(b,a)\rbrace +\lbrace (a,a)\rbrace +\lbrace (b,b)\rbrace\\
&+\lbrace (a,b,a)\rbrace +\lbrace (a,b,b)\rbrace +\lbrace (a,a,b)\rbrace\\
&+\lbrace (b,b,a)\rbrace +\lbrace (b,a,b)\rbrace +\lbrace (b,b,b)\rbrace +\lbrace (a,a,a)\rbrace +\lbrace (b,a,a)\rbrace\\
&+\cdots
\end{aligned}
\]
可以看到 \(\lbrace (a,b)\rbrace ,\lbrace (b,a)\rbrace\) 這樣組成部分的順序不同的元素被生成了，可以認為 Sequence 構造生成了有序的組合。
我們定義
\[
\operatorname{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}=\lbrace \bullet\rbrace\times\operatorname{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{aligned}
\operatorname{MSET}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\
\operatorname{MSET}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\
&+\lbrace b\rbrace +\lbrace (a,b)\rbrace +\lbrace (a,a,b)\rbrace +\cdots \\
&+\lbrace (b,b)\rbrace + \lbrace (a,b,b)\rbrace +\lbrace (a,a,b,b)\rbrace + \cdots\\
&+\cdots
\end{aligned}
\]
注意到 \(\lbrace (b,a)\rbrace,\lbrace (a,b,a)\rbrace\) 在 \(\operatorname{SEQ}(\lbrace a,b\rbrace)\) 中出現，但在 \(\operatorname{MSET}(\lbrace a,b\rbrace)\) 沒有出現，可以認為 Multiset 生成了無序的組合。
我們定義其遞推式為
\[
\operatorname{MSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_n\rbrace)=\operatorname{MSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_{n-1}\rbrace)\times \operatorname{SEQ}(\lbrace \alpha_n\rbrace)
\]
即
\[
\operatorname{MSET}(\mathcal{A})=\prod _ {\alpha\in\mathcal{A}}\operatorname{SEQ}(\lbrace \alpha\rbrace)
\]
且要求 \(\mathcal{A}_0=\varnothing\)。或者也可以給出等價的
\[
\operatorname{MSET}(\mathcal{A})=\operatorname{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 為
\[
\operatorname{Exp}(A(z))=\prod _ {\alpha \in\mathcal{A}}\left(1-z^{\lvert \alpha \rvert}\right)^{-1}=\prod _ {n\geq 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\geq 1}\frac{(-1)^{n-1}z^n}{n}
\]
且 \(A(z)=\exp(\ln(A(z)))\) 所以
\[
\begin{aligned}
\operatorname{Exp}(A(z))&=\exp\left(\sum _ {n\geq 1}-a_n\cdot \ln\left(1-z^n\right)\right)\\
&=\exp\left(\sum _ {n\geq 1}-a_n\cdot \sum _ {m\geq 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{aligned}
\]
其中 \(\operatorname{Exp}\) 為 Pólya 指數，也被稱為 Euler 變換。
例題 LOJ 6268. 分拆數
題意：令 \(f(n)\) 表示將 \(n\) 進行分拆的方案數，求 \(f(1),f(2),\dots,f(10^5)\) 對 \(998244353\) 取模的值。
解：設全體正整數類為 \(\mathcal{I}\)，那麼 \(\mathcal{I}=\operatorname{SEQ}_{\geq 1}(\mathcal{Z})=\mathcal{Z}\times \operatorname{SEQ}(\mathcal{Z})\)（下標 \(\geq 1\) 為有限制的構造，見後文）。所求即
\[
\operatorname{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\leq n,m\leq 10^5\) 且 \(1\leq v_i\leq m\)。
解：設商品的組合類為 \(\mathcal{A}\)，所求即 \(\operatorname{MSET}(\mathcal{A})\) 對應 OGF 的係數。
例題 洛谷 P5900 無標號無根樹計數
題意：求出 \(n\) 個節點的無標號無根樹的個數對 \(998244353\) 取模的值。約定 \(1\leq n\leq 2\times 10^5\)。
解：設無標號有根樹的組合類為 \(\mathcal{T}\)，那麼
\[
\mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{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{aligned}
\operatorname{PSET}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace \\
\operatorname{PSET}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace b\rbrace +\lbrace (a,b)\rbrace \\
\operatorname{PSET}(\lbrace a,b,c\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace b\rbrace +\lbrace (a,b)\rbrace +\lbrace c\rbrace +\lbrace (a,c)\rbrace +\lbrace (b,c)\rbrace +\lbrace (a,b,c)\rbrace\\
\end{aligned}
\]
我們定義其遞推式為
\[
\operatorname{PSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_n\rbrace)=\operatorname{PSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_{n-1}\rbrace)\times (\lbrace \epsilon\rbrace +\lbrace \alpha_n\rbrace)
\]
即
\[
\operatorname{PSET}(\mathcal{A})\cong \prod _ {\alpha\in\mathcal{A}}\left(\lbrace \epsilon \rbrace +\lbrace \alpha\rbrace\right)
\]
且要求 \(\mathcal{A}_0=\varnothing\)。
對應 OGF 為
\[
\begin{aligned}
\overline{\operatorname{Exp}}(A(z))&=\prod _ {\alpha\in\mathcal{A}}\left(1+z^{\lvert \alpha \rvert}\right)=\prod _ {n\geq 1}\left(1+z^n\right)^{a_n}\\
&=\exp\left(\sum _ {n\geq 1}a_n\cdot \ln\left(1+z^n\right)\right)\\
&=\exp\left(\sum _ {n\geq 1}a_n\cdot \sum _ {m\geq 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{aligned}
\]
其中 \(\overline{\operatorname{Exp}}\) 為 Pólya 指數·改。
容易發現 \(\operatorname{PSET}(\mathcal{A})\subset \operatorname{MSET}(\mathcal{A})\)。
集合的 Cycle 構造
Cycle 構造生成了所有可能的組合，但不區分僅輪換不同的組合。
我們定義為
\[
\operatorname{CYC}(\mathcal{A})=\left(\operatorname{SEQ}(\mathcal{A})\setminus\lbrace \epsilon\rbrace\right)/\mathbf{S}
\]
其中 \(\mathbf{S}\) 為等價關係，我們説 \((\alpha_1,\dots,\alpha_n)\mathbf{S}(\beta_1,\dots,\beta_n)\) 當且僅當存在任一循環移位 \(\tau\) 對於所有 \(j\) 都滿足 \(\beta_j=\alpha_{\tau(j)}\)。
例
為了簡便我們令 \(\texttt{a},\texttt{b}\) 均為大小為 \(1\) 的字符，這裏僅列舉大小為 \(3\) 和 \(4\) 的字符串：
\[
\operatorname{CYC}(\lbrace \texttt{a},\texttt{b}\rbrace)_3=\lbrace \texttt{aaa}\rbrace +\lbrace \texttt{aab}\rbrace+\lbrace \texttt{abb}\rbrace+\lbrace \texttt{bbb}\rbrace
\]
其中 \(\texttt{aab}\mathbf{S}\texttt{baa}\mathbf{S}\texttt{aba}\) 只保留其一，同樣的 \(\texttt{abb}\mathbf{S}\texttt{bab}\mathbf{S}\texttt{bba}\) 只保留其一。
\[
\operatorname{CYC}(\lbrace \texttt{a},\texttt{b}\rbrace)_4=\lbrace \texttt{aaaa}\rbrace +\lbrace \texttt{aaab}\rbrace+\lbrace \texttt{aabb}\rbrace+\lbrace \texttt{abbb}\rbrace+\lbrace \texttt{bbbb}\rbrace +\lbrace \texttt{abab}\rbrace
\]
其中 \(\texttt{aaab}\mathbf{S}\texttt{baaa}\mathbf{S}\texttt{abaa}\mathbf{S}\texttt{aaba}\)，\(\texttt{aabb}\mathbf{S}\texttt{baab}\mathbf{S}\texttt{bbaa}\mathbf{S}\texttt{abba}\)，\(\texttt{abbb}\mathbf{S}\texttt{babb}\mathbf{S}\texttt{bbab}\mathbf{S}\texttt{bbba}\) 和 \(\texttt{abab}\mathbf{S}\texttt{baba}\)。
對應 OGF 為
\[
\operatorname{Log}(A(z))=\sum _ {n\geq 1}\frac{\varphi(n)}{n}\ln\frac{1}{1-A(z^n)}
\]
其中 \(\varphi\) 為 Euler 函數，\(\operatorname{Log}\) 為 Pólya 對數。
由於證明較複雜，讀者可參考 Flajolet 的論文 The Cycle Construction 或 Analytic Combinatorics 的附錄。
有限制的構造
對於上述所有構造，我們都沒有限制其「組成部分」的個數，若在 \(\operatorname{SEQ}\) 的下標給一個作用於整數的謂詞用於約束其組成部分，如
\[
\operatorname{SEQ}_{=k}(\mathcal{B}),\quad \operatorname{SEQ}_{\geq k}(\mathcal{B}),\quad \operatorname{SEQ}_{1..k}(\mathcal{B})
\]
其中 \(\operatorname{SEQ}_{=k}(\mathcal{B})\) 也常簡寫為 \(\operatorname{SEQ}_k(\mathcal{B})\)，\(\operatorname{SEQ}_{1..k}(\mathcal{B})\) 表示在區間 \(\lbrack 1..k\rbrack\) 上。
令 \(\mathfrak{K}\) 為任意上述 \(\operatorname{SEQ},\operatorname{PSET},\operatorname{MSET},\operatorname{CYC}\) 之一，以及
\[
\mathcal{A}=\mathfrak{K}_k(\mathcal{B})
\]
即我們需要對於 \(\alpha\in\mathcal{A}\) 有
\[
\alpha =\lbrace (\beta_1,\beta_2,\dots ,\beta_k)\mid \beta\in\mathcal{B}\rbrace
\]
設 \(\chi\) 函數作用於組合對象上為其組成部分的個數，也就是要令 \(\chi(\alpha)=k\)，不妨增加一元來「跟蹤」組成部分的個數。
令
\[
A _ {n,k}=\operatorname{card}\left\lbrace \alpha\in\mathcal{A}\mid \lvert \alpha\rvert =n,\chi(\alpha)=k\right\rbrace
\]
那麼
\[
A(z,u)=\sum _ {n,k}A _ {n,k}u^kz^n=\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert}u^{\chi(\alpha)}
\]
然後我們只要提取出 \(u^k\) 的係數即可獲得對應表達式，例如 \(\mathcal{A}=\operatorname{SEQ}_k(\mathcal{B})\) 可直接導出
\[
\begin{aligned}
&{}A(z,u)=\sum _ {k\geq 0}u^kB(z)^k=\frac{1}{1-uB(z)}\\
\implies &{}A(z)=B(z)^k
\end{aligned}
\]
顯然也有
\[
\mathcal{A}=\operatorname{SEQ}_{\geq k}(\mathcal{B})\implies A(z)=\frac{B(z)^k}{1-B(z)}
\]
而對於 \(\operatorname{MSET} _ k(\mathcal{B})\) 和 \(\operatorname{PSET} _ k(\mathcal{B})\) 已經有
\[
\begin{aligned}
&{}A(z,u)=\prod_n\left(1-uz^n\right)^{-b_n}\\
\implies &{}A(z)=\lbrack u^k\rbrack \exp\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots\right)
\end{aligned}
\]
和
\[
\begin{aligned}
&{}A(z,u)=\prod_n\left(1+uz^n\right)^{b_n}\\
\implies &{}A(z)=\lbrack u^k\rbrack \exp\left(\frac{u}{1}B(z)-\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)-\cdots\right)
\end{aligned}
\]
對於 \(\operatorname{CYC}_k(\mathcal{B})\) 同理。
使用上式計算 \(\operatorname{MSET}_3(\mathcal{B})\) 和 \(\operatorname{MSET}_4(\mathcal{B})\) 對應 OGF
嘗試計算 \(\mathcal{A}=\operatorname{MSET}_3(\mathcal{B})\) 為
\[
\begin{aligned}
\lbrack u^3\rbrack A(z,u)&= \frac{1}{0!}\left(\lbrack u^3\rbrack 1\right)+\frac{1}{1!}\left(\lbrack u^3\rbrack \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(\lbrack u^3\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)^2\right)\\
&+\frac{1}{3!}\left(\lbrack u^3\rbrack \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{aligned}
\]
嘗試計算 \(\mathcal{A}=\operatorname{MSET}_4(\mathcal{B})\) 為
\[
\begin{aligned}
\lbrack u^4\rbrack A(z,u)&= \frac{1}{0!}\left(\lbrack u^4\rbrack 1\right)+\frac{1}{1!}\left(\lbrack u^4\rbrack \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(\lbrack u^4\rbrack \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(\lbrack u^4\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)^3\right)\\
&+\frac{1}{4!}\left(\lbrack u^4\rbrack \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)^2B(z^2)}{2}\right)+\frac{B(z)^4}{4!}\\
&=\frac{B(z)^4}{24}+\frac{B(z)^2B(z^2)}{4}+\frac{B(z)B(z^3)}{3}+\frac{B(z^2)^2}{8}+\frac{B(z^4)}{4}
\end{aligned}
\]
我們發現 \(\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{aligned}
\operatorname{PSET} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}-\frac{A(z^2)}{2}\\
\operatorname{MSET} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}+\frac{A(z^2)}{2}\\
\operatorname{CYC} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}+\frac{A(z^2)}{2}
\end{aligned}
\]
\[
\begin{aligned}
\operatorname{PSET} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{6}-\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\
\operatorname{MSET} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{6}+\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\
\operatorname{CYC} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{3}+\frac{2A(z^3)}{3}\\
\end{aligned}
\]
\[
\begin{aligned}
\operatorname{PSET} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{24}-\frac{A(z)^2A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2)^2}{8}-\frac{A(z^4)}{4}\\
\operatorname{MSET} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{24}+\frac{A(z)^2A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2)^2}{8}+\frac{A(z^4)}{4}\\
\operatorname{CYC} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{4}+\frac{A(z^2)^2}{4}+\frac{A(z^4)}{2}\\
\end{aligned}
\]
上面的計算方法雖然有效但比較麻煩，讀者可閲讀 WolframMathWorld 網站的 Pólya Enumeration Theorem 和 Cycle Index 等相關資料，後者 Cycle Index 在 OEIS 的生成函數表達式中也經常出現。
例題 LOJ 6538. 烷基計數 加強版 加強版
題意：求出 \(n\) 個節點的有根且根節點度數不超過 \(3\)，其餘節點度數不超過 \(4\) 的無序樹的個數對 \(998244353\) 取模的值。約定 \(1\leq n\leq 10^5\)。
解：設組合類為 \(\mathcal{T}\) 那麼
\[
\mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{MSET}_{0,1,2,3}(\mathcal{T})
\]
或令組合類 \(\hat{\mathcal{T}}=\mathcal{T}+\lbrace \epsilon\rbrace\) 那麼
\[
\hat{\mathcal{T}}=\lbrace \epsilon\rbrace +\lbrace \bullet\rbrace\times\operatorname{MSET}_{3}(\hat{\mathcal{T}})
\]
可得到相同的結果。
參考文獻
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用