也许更好的阅读体验

一般生成函数(OGF)

引入

考虑一类组合对象组成的集合 $A$A，其中：

• 每个元素 $a\in A$a∈A都被定义了“大小” $\mid a\mid$∣a∣，它是一个非负整数。
• 对于给定的 $n$n，大小为 $n$n的元素的数量是有限的，记作 $A_n$An​

eg. $A$A是全体 $01$01串组成的集合，一个 $01$01串的大小被定义为它的长度则 $A_n=2^n$An​=2n

定义

$A\left(x\right)={\sum }_{i=0}^{\infty }{A}_i{x}^i$A(x)=∑i=0∞​Ai​xi
为 $A$A的一般生成函数
注意

• $A\left(x\right)$A(x)为一个多项式
• 这里的 $A_i$Ai​为第 $i$i项的 系数

这是一个形式幂级数，不用考虑何时收敛
这里的 $x^i$xi为形式幂，无实义，一般也不会去求
但是 $x^i$xi有区分实际意义的作用，即 $x^i\to$xi→第 $i$i项
$x^i$xi的系数为第 $i$i种状态的答案
这个不好说，举个例子
eg.
$A$A是全体 $01$01串组成的集合，则
$\begin{array}{c}{\displaystyle A\left(x\right)=\sum _{i=0}^{\infty }{2}^i{x}^i}\end{array}=\frac{1}{1-2x}$A(x)=i=0∑∞​2ixi​=1−2x1​
最后一步是用的等比数列求和公式，不用考虑何时收敛，所以认为其很大是趋近于0
其中 $A_i=2^i$Ai​=2i，表示长度为 $i$i的答案为 $2^i$2i
$x^i$xi的系数就是长度为 $i$i的答案，它是用于区分这个的

运算

有两类组合对象 $A$A和 $B$B

• 定义 $C$C为 $A$A和 $B$B的并集
  $C\left(x\right)=A\left(x\right)+B\left(x\right)，O\left(n\right)$C(x)=A(x)+B(x)，O(n)计算
• 定义 $D$D为 $A$A和 $B$B的笛卡尔积，也即 $D$D中每个元素 $d$d都是 $A$A中某元素 $a$a与 $B$B中某元素 $b$b拼成的二元组 $(a,b)$(a,b)，其大小 $\mid d\mid$∣d∣ 定义为 $\mid a\mid +\mid b\mid$∣a∣+∣b∣
  $D\left(x\right)=A\left(x\right)B\left(x\right)$D(x)=A(x)B(x)， $FFT$FFT乘法 $O\left(nlogn\right)$O(nlogn)计算

eg:
$A$A是全体 $01$01串组成的集合， $B$B是全体字母组成的集合

$\begin{array}{c}{\displaystyle A\left(x\right)=\sum _{i=0}^{\infty }{2}^i{x}^i}\end{array}=\frac{1}{1-2x}$A(x)=i=0∑∞​2ixi​=1−2x1​
$\begin{array}{c}{\displaystyle B\left(x\right)=\sum _{i=0}^{\infty }26^i{x}^i}\end{array}=\frac{1}{1-26x}$B(x)=i=0∑∞​26ixi​=1−26x1​

$C\left(x\right)=A\left(x\right)+B\left(x\right)$C(x)=A(x)+B(x)， $C\left(x\right)$C(x)表示全体 $01$01串与全体字母的并集
$C\left(x\right)$C(x)中 $x^i$xi项的系数表示长度为 $i$i的 $01$01串与字符串有多少

$D\left(x\right)=A\left(x\right)B\left(x\right)$D(x)=A(x)B(x)， $D\left(x\right)$D(x)表示 $01$01串与字符串拼接出的串（前面是 $01$01串，后面是字符串）
$D\left(x\right)$D(x)中 $x^i$xi项的系数表示长度为 $i$i的拼接出的串有多少
其中某串长度可以为0

个人理解

我们发现上面的例题中的 $D$D如果我们不考虑多项式
自己暴力的去算，也有这样的公式
$\begin{array}{c}{\displaystyle \sum _{i+j=n}{a}_i{b}_j}\end{array}$i+j=n∑​ai​bj​​
其中 $a_i$ai​表示长度为 $i$i的 $01$01串有多少种， $b_j$bj​表示长度为 $j$j的字符串有多少种
然后我们可以发现长度 $i+j$i+j的答案会由 $i$i与 $j$j项得到，再发现其与指数乘法有相似之处，即 $x^i{x}^j=x^{i+j}$xixj=xi+j，之后就想到将答案存为其系数， $x^i$xi表示实际意义，于是就可以用多项式来解决问题，因为多项式可以 $FFT$FFT优化，比暴力快很多
(我觉得生成函数可能就是这么来的…)

指数生成函数(EGF)

引入

有时我们需要考虑带标号的组合对象，比如图
$n$n个点的标号图，顶点的标号恰好为 $1\sim n$1∼n

带标号对象的拼接

将两个对象 $a;b$a;b拼接起来， $\mid a\mid =n，\mid b\mid =m$∣a∣=n，∣b∣=m

• 无标号时，只有一种方法
• 带标号时，规定拼接时拼接对象内部相对标号顺序不变，而互相的标号
  可以改变，则有 $C_{n+m}^n\left(\left(\begin{array}{c}n+m\\ n\end{array}\right)\right)$Cn+mn​((n+mn​))种拼接方法
  因为只要考虑前 $a$a中的 $n$n个用了哪些标号，剩下的 $m$m个给 $b$b中的 $m$m个，答案唯一，而对象内部相对标号顺序不变，所以得到的标号如何分配也是唯一的
  eg.
  将 $213,21$213,21(每个数字是一个标号)拼接，有 $10$10种方法
  数字表示分配的标号
  $435,21\mid 425,31\mid 325,41\mid 324,51\mid 415,32$435,21∣ 425,31∣ 325,41∣ 324,51∣ 415,32
  $315,42\mid 314,52\mid 215,43\mid 214,53\mid 213,54$315,42∣ 314,52∣ 215,43∣ 214,53∣ 213,54
  如第一种方案 $435$435对应的 $231$231相对标号顺序不变， $31$31对应的 $21$21相对标号顺序也不变

定义

对于带标号组合对象组成的集合 $A$A，定义
$\begin{array}{c}{\displaystyle A\left(x\right)=\sum _{i=0}^n{A}_i\frac{x^i}{i!}}\end{array}$A(x)=i=0∑n​Ai​i!xi​​
为 $A$A的指数生成函数

运算

有两类组合对象 $A$A和 $B$B

• 定义 $C$C为 $A$A和 $B$B的并集
  $C\left(x\right)=A\left(x\right)+B\left(x\right)，O\left(n\right)$C(x)=A(x)+B(x)，O(n)计算
• 定义 $D$D为 $A$A和 $B$B的笛卡尔积，也即 $D$D中每个元素 $d$d都是 $A$A中某元素 $a$a与 $B$B中某元素 $b$b拼成的二元组 $(a,b)$(a,b)，其大小 $\mid d\mid$∣d∣ 定义为 $\mid a\mid +\mid b\mid$∣a∣+∣b∣
  $D\left(x\right)=A\left(x\right)B\left(x\right)$D(x)=A(x)B(x)， $FFT$FFT乘法 $O\left(nlogn\right)$O(nlogn)计算

没错，就是复制上面的内容
对于 $D\left(x\right)$D(x)
$\begin{array}{c}{\displaystyle D\left(x\right)=\sum _{i+j=n}{A}_i{B}_j\frac{(i+j)!}{i!j!}}\end{array}$D(x)=i+j=n∑​Ai​Bj​i!j!(i+j)!​​
$\begin{array}{c}{\displaystyle \frac{D\left(x\right)}{n!}=\sum _{i+j=n}\frac{Ai}{i!}\frac{B_j}{j!}}\end{array}$n!D(x)​=i+j=n∑​i!Ai​j!Bj​​​
所以乘法运算成立

个人理解

如引入中的问题
用一般生成函数来求解
$\begin{array}{c}{\displaystyle D\left(x\right)=A\left(x\right)B\left(x\right)=\sum _{i+j=n}^n{A}_i\cdot B_j\left(\begin{array}{c}n\\ i\end{array}\right)}\end{array}$D(x)=A(x)B(x)=i+j=n∑n​Ai​⋅Bj​(ni​)​
最后又化简成

$\begin{array}{c}{\displaystyle \frac{D\left(x\right)}{n!}=\sum _{i+j=n}\frac{Ai}{i!}\frac{B_j}{j!}}\end{array}$n!D(x)​=i+j=n∑​i!Ai​j!Bj​​​
于是我们就弄出一个指数生成函数方便运算且省去求组合数

以下 $A$A为生成函数

生成序列(seq)

如字面意思，要生成一个序列
序列的顺序是确定的
$\begin{array}{c}{\displaystyle seq\left(A\right)=\sum _{i=0}^{\infty }Ai=\frac{1}{1-A}}\end{array}$seq(A)=i=0∑∞​Ai=1−A1​​

生成集合(set)

如字面意思，要生成一个集合
集合的顺序是无关紧要的，所以要除以全排列

$\begin{array}{c}{\displaystyle set\left(A\right)=\sum _{i=0}^{\infty }\frac{A^i}{i!}=e^A}\end{array}$set(A)=i=0∑∞​i!Ai​=eA​

最后一步是因为该式子符合 $e^x$ex的泰勒展开
关于泰勒展开可看我的该篇博客泰勒公式于牛顿迭代

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧