一般生成函数(OGF)
引入
考虑一类组合对象组成的集合(A)，其中：
- 每个元素(ain A)都被定义了“大小”(|a|)，它是一个非负整数。
- 对于给定的(n)，大小为(n)的元素的数量是有限的，记作(A_n)
eg. (A)是全体(01)串组成的集合，一个(01)串的大小被定义为它的长度则(A_n=2^n)
定义
(Aleft( x
ight) =sum ^{infty }_{i=0}A_ix^{i})
为(A)的一般生成函数
注意
- (A(x))为一个多项式
- 这里的(A_i)为第(i)项的 系数
这是一个形式幂级数，不用考虑何时收敛
这里的(x^i)为形式幂，无实义，一般也不会去求
但是(x^i)有区分实际意义的作用，即(x^i
ightarrow)第(i)项
(x^i)的系数为第(i)种状态的答案
这个不好说，举个例子
eg.
(A)是全体(01)串组成的集合，则
(egin{aligned}Aleft( x
ight) =sum ^{infty }_{i=0}2^{i}x^{i}end{aligned}=dfrac{1}{1-2x})
最后一步是用的等比数列求和公式，不用考虑何时收敛，所以认为其很大是趋近于0
其中(A_i=2^i)，表示长度为(i)的答案为(2^i)
(x^i)的系数就是长度为(i)的答案，它是用于区分这个的
运算
有两类组合对象(A)和(B)
- 定义(C)为(A)和(B)的并集
(C(x) =A(x) +B(x)，O(n))计算 - 定义(D)为(A)和(B)的笛卡尔积，也即(D)中每个元素(d)都是(A)中某元素(a)与(B)中某元素(b)拼成的二元组((a,b))，其大小(|d|) 定义为(|a|+|b|)
(D(x) =A(x)B(x))，(FFT)乘法(O(nlogn))计算
eg:
(A)是全体(01)串组成的集合，(B)是全体字母组成的集合
(egin{aligned}Aleft( x
ight) =sum ^{infty }_{i=0}2^{i}x^{i}end{aligned}=dfrac{1}{1-2x})
(egin{aligned}Bleft( x
ight) =sum ^{infty }_{i=0}26^{i}x^{i}end{aligned}=dfrac{1}{1-26x})
(C(x)=A(x)+B(x))，(C(x))表示全体(01)串与全体字母的并集
(C(x))中(x^i)项的系数表示长度为(i)的(01)串与字符串有多少
(D(x)=A(x)B(x))，(D(x))表示(01)串与字符串拼接出的串（前面是(01)串，后面是字符串）
(D(x))中(x^i)项的系数表示长度为(i)的拼接出的串有多少
其中某串长度可以为0
个人理解
我们发现上面的例题中的(D)如果我们不考虑多项式
自己暴力的去算，也有这样的公式
(egin{aligned}sum_{i+j=n}a_ib_jend{aligned})
其中(a_i)表示长度为(i)的(01)串有多少种，(b_j)表示长度为(j)的字符串有多少种
然后我们可以发现长度(i+j)的答案会由(i)与(j)项得到，再发现其与指数乘法有相似之处，即(x^ix^j=x^{i+j})，之后就想到将答案存为其系数，(x^i)表示实际意义，于是就可以用多项式来解决问题，因为多项式可以(FFT)优化，比暴力快很多
(我觉得生成函数可能就是这么来的.....)
指数生成函数(EGF)
引入
有时我们需要考虑带标号的组合对象，比如图
(n)个点的标号图，顶点的标号恰好为(1sim n)
带标号对象的拼接
将两个对象(a;b)拼接起来，(|a|=n，|b|=m)
- 无标号时，只有一种方法
- 带标号时，规定拼接时拼接对象内部相对标号顺序不变，而互相的标号
可以改变，则有(C_{n+m}^{n}(egin{pmatrix} n+m \ n end{pmatrix}))种拼接方法
因为只要考虑前(a)中的(n)个用了哪些标号，剩下的(m)个给(b)中的(m)个，答案唯一，而对象内部相对标号顺序不变，所以得到的标号如何分配也是唯一的
eg.
将(213,21)(每个数字是一个标号)拼接，有(10)种方法
数字表示分配的标号
(435,21| 425,31| 325,41| 324,51| 415,32)
(315,42| 314,52| 215,43| 214,53| 213,54)
如第一种方案(435)对应的(231)相对标号顺序不变，(31)对应的(21)相对标号顺序也不变
定义
对于带标号组合对象组成的集合(A)，定义
(egin{aligned}Aleft( x
ight) =sum _{i= 0}^nA_{i}dfrac {x^{i}}{i!}end{aligned})
为(A)的指数生成函数
运算
有两类组合对象(A)和(B)
- 定义(C)为(A)和(B)的并集
(C(x) =A(x) +B(x)，O(n))计算 - 定义(D)为(A)和(B)的笛卡尔积，也即(D)中每个元素(d)都是(A)中某元素(a)与(B)中某元素(b)拼成的二元组((a,b))，其大小(|d|) 定义为(|a|+|b|)
(D(x) =A(x)B(x))，(FFT)乘法(O(nlogn))计算
没错，就是复制上面的内容
对于(D(x))
(egin{aligned}D(x)=sum _{i+j=n}A_{i}B_{j}dfrac {left( i+j
ight) !}{i!j!}end{aligned})
(egin{aligned}dfrac {D(x)}{n!}=sum _{i+j=n}dfrac {Ai}{i!}dfrac {B_{j}}{j!}end{aligned})
所以乘法运算成立
个人理解
如引入中的问题
用一般生成函数来求解
(egin{aligned}Dleft( x
ight) =Aleft( x
ight) Bleft( x
ight) =sum ^{n}_{i+j=n}A_{i}cdot B_{j}egin{pmatrix} n \ i end{pmatrix}end{aligned})
最后又化简成
(egin{aligned}dfrac {D(x)}{n!}=sum _{i+j=n}dfrac {Ai}{i!}dfrac {B_{j}}{j!}end{aligned})
于是我们就弄出一个指数生成函数方便运算且省去求组合数
以下(A)为生成函数
生成序列(seq)
如字面意思，要生成一个序列
序列的顺序是确定的
(egin{aligned}seqleft( A
ight) =sum ^{infty }_{i=0}Ai=dfrac {1}{1-A}end{aligned})
生成集合(set)
如字面意思，要生成一个集合
集合的顺序是无关紧要的，所以要除以全排列
(egin{aligned}setleft( A ight) =sum ^{infty }_{i=0}dfrac{A^i}{i!}=e^Aend{aligned})
最后一步是因为该式子符合(e^x)的泰勒展开
关于泰勒展开可看我的该篇博客泰勒公式于牛顿迭代
如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧