生成函数入门

· · 个人记录

生成函数

什么是生成函数

生成函数的另一种表示方法

我们常常能观察到，有一些数列的生成函数具有一些性质

比如如下的生成函数A：

A(x)=1+x^1+x^2+x^3+....

该生成函数的各个项构成了一个等比数列

按照等比数列求和的公式，我们可以把如上的生成函数表示为

A(x)=\frac{1-x^n}{1-x}

由于生成函数是一个形式幂级数，讨论x的取值在这里没有任何意义，我们不妨令x \in(-1,1)，这样x^n这一项就可以直接消掉了，那么

A(x)=\frac{1}{1-x}

通过这样的方式，我们把一个无限长的用多项式形式表达的生成函数成功的用一个极简短的函数表示了

另外这种化简还可以通过广义二项式定理等实现

一般生成函数的运算性质

之前提到，生成函数作为描述集合/数列的一种语言，拥有一些独特的性质，这与它的运算是息息相关的

一般生成函数的加法运算

定义加法运算+，作用于两个集合A,B，若C=A+B，则认为C是A,B两集合的并集

在这个意义下，集合C的生成函数就是集合A,B生成函数按位相加的和也就是C(x)=A(x)+B(x)

举一个例子：

数列A=\{1,1,1\}代表物品A只能选0,1,2件，其生成函数为A(x)=1+x+x^2

无限长数列B=\{1,0,1,0,1,0...\}代表物品B只能选偶数件，其生成函数为B(x)=1+x^2+x^4+x^6+...

考虑如果我们把以上两个数列的生成函数相加，得到的新的生成函数具有什么性质呢？

先列出C的生成函数

C(x)=2x^0+1x+2x^2+0x^3+x^4+0x^5+x^6......

这个生成函数的含义是：选0件物品有2种方法，选1件物品有1种方法，选2件物品有2种方法......但还有一个限制条件：每次选物品时要么选A要么选B，不能两者同时选

为什么会有上文的限制条件呢？因为C的生成函数是由A和B两者的生成函数单纯的相加构成的，实际上两者还是分开的

这样的运算在平时当然没什么应用价值，我们一般想知道的是：把这些物品混到一起，在满足每个物品的限制情况下，取若干件物品的方案数

一般生成函数的卷积运算

于是我们定义新运算卷积运算*，同样作用于两个集合，若C=A*B，则认为C是A,B两集合的笛卡尔积

笛卡尔积也是一个集合，这个集合内部的所有元素可以看做是一个二元组<a,b>，其中a\in A,b\in B

还是考虑上面的例子，由于无限长数列不好卷积，重新定义B数列为\{0,2,4,6\}，意即B物品只能取0,2,4,6件

我们对数列A的生成函数与数列B的生成函数做一次卷积

得到新的C的生成函数

C(x)=1+x+2x^2+x^3+2x^4+x^5+x^6

这个生成函数就可以很好的满足我们上面的要求了

至于为什么会是这样？这里多项式的优势就体现出来了，两个单项式相乘，指数相加，实际上就相当于选择了这两个单项式所代表的物品

另外，生成函数的多项式形式还有一个巨大的优势：在计算卷积时可以使用FFT进行优化，复杂度达到优秀的O(nlogn)

一般生成函数的生成序列

若集合A 中没有大小为0的元素

对A的生成函数定义它的生成序列seq(A)=1+A+A^2+A^3+...=\frac{1}{1-A}

生成序列的意义是：集合A中的元素任意排列成的序列组成的集合

生成序列的定义可以帮助我们解决不少的组合问题

考虑下面的一个问题

设整数n为若干个变量x的和，即n=x_1+x_1+x_3+...

问这个方程有多少个不同的非负整数解

我们换一个角度思考这个问题，可以看作是选取k件体积为0,1,2,3...\infty的物品，每件物品数量不限，要求恰好装满体积为n的背包的方案数

我们对这个物品的集合构造一个生成函数

A(x)=1+x^1+x^2+x^3+... 那么我们求出$A$的生成序列，其中第$n$项的系数$seq(A)_n$即为方案数 ## 关于指数型生成函数$(EGF)

一般生成函数多数应用于解决可重集组合问题

也就是从可重集中选择若干个元素组成一个新的元素的方案数，这里选择的元素的顺序是不会影响最终的答案的

对于这一类问题，我们一般采用如下步骤：

但有时候题目要求的东西与排列有关，这时选择元素的顺序也会对最终的答案产生影响

这时候我们就不能用一般生成函数进行解决了， 引入一个新概念指数型生成函数

指数型生成函数可以很方便的解决可重集的排列问题

什么叫可重集的排列问题呢？下面举一个经典的例子

若n=m_1 \times a_1+m_2 \times a_2+...+m_k \times a_k

观察到组成n的元素出现的次数可能大于一，这里我们就将n称为一个可重集

易知可重集n的全排列个数为\frac{n!}{m_1!m_2!...m_k!}

但我们如果想从n中选出r个元素，求这r个元素的排列个数，由于我们不知道选出的r个元素的具体情况，我们就无法直接用组合数求解了

考虑构造这个可重集的指数型生成函数

若我们把指数型生成函数的在x^n处系数视作选择n个元素得到的可能的排列数

那么对于同一种元素——也就是出现m_i次的元素a_i

我们可以构造指数型生成函数A_i(x)=x+x^2+x^3+...x^{m_i}

各个项的系数均为1，因为元素种类相同，长度固定的排列只有一种

模仿一般生成函数OGF的卷积过程，假设我们现在有两个分别对于元素a_i,a_j的指数型生成函数A,B，求D=A*B

如果按照$OGF$的方式直接进行卷积，那么我们得到的还只是**可重集的组合**而非**排列** 那么，在卷积中对于一次$x^m,x^n$的相乘，我们是不是只要乘上一个$(m+n)!$是不是就转化为排列了呢？ 即 $$D_n=\sum_{i+j=n}A_iB_j(i+j!)$$ 我们会发现这样求出的答案还是错的，会比预期的答案要大 这是由于我们计算了许多重复的方案 解决这个问题，我们可以给相同种类的元素内部进行标号，在合并时限制同种元素的内部相对标号顺序不变，而不同元素间的标号任意就可以除去重复的方案了 也就是说 $$D_n=\sum_{i+j=n}A_iB_j \times C_n^i=\sum_{i+j=n}A_iB_j \times C_{i+j}^i$$ 如果我们把这个组合数进行展开 $$C_{i+j}^i=\frac{(i+j)!}{i!j!}$$ 发现完全可以与之前的式子配合形成一个非常优美的式子，即 $$\frac{D_{i+j}}{(i+j)!}=\sum_{i+j=n}\frac{A_i}{i!}\cdot \frac{B_j}{j!}$$ 这样可以完美消去组合数的影响，也启发了我们对指数型生成函数进行定义 那么定义对于带标号组合对象的集合$A$，其指数型生成函数为 $$A(x)=\sum_{i=0}^{\infty}A_i\frac{x^i}{i!}$$ 其中$A_i$与$\frac{1}{i!}$共同构成第$x^i$项的系数，而$A_i$代表的是选择$i$个元素可能的排列个数 既然有了指数型生成函数这一利器，我们如何解决上面的问题呢 对于每一类元素构造一个指数型生成函数，最后每一类元素的指数型生成函数卷积起来，得到的新的生成函数的第$x^n$项的$A_n$即为选择$n$个元素得到的可能的排列个数 即 $$A(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^{m_1}}{m_1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^{m_2}}{m_2!})...(1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^{m_k}}{m_k!})$$ 将上式整理后同类项合并即可得到对于该**可重集排列**的生成函数 ## 指数型生成函数的运算性质 ### 指数型生成函数的加法与卷积运算 由于在定义中已经消去了重复方案的影响，加法与卷积运算与$OGF$相同 ### 指数型生成函数的生成序列 $$seq(A)=\sum_{i=0}^{\infty}A^i=\frac{1}{1-A}$$ 生成序列的顺序是有影响的 ### 指数型生成函数的生成集合 $$set(A)=\sum_{i=0}^{\infty}\frac{A^i}{i!}=e^A$$ 生成集合的顺序是无关的 至于为什么是$e^A$我也不清楚好像是泰勒展开