生成函数学习笔记

本文参考博客：巨佬的blog

是什么

处理排列组合问题的有效工具，可以应对巨大无比的$n$（比如$1e9999 \sim 1e10000 $)(luoguP2000)
在百度百科上定义如下：

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出。生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导Fibonacci数列的通项公式方法之一。另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进。

在维基百科上定义如下：

在数学中，某个序列(an)n∈N 的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

简单来说，就是对于一个已知的数列，使用一个函数来表示他，其中$x ^ i$对应的系数$a_i$即为原数列的第$i$位。
例如设一个函数$G(x) = a_0 + a_1x + a_2x^2 + … +a_nx^n$，那么他的系数就是原数列$a_0,a_1,a_2 … a_n$
所以函数中的自变量并无实际意义，其取值不影响函数对于原数列的表示作用。我们称这样的函数为形式幂级数

为什么

那么讲讲使用生成函数有哪些好处：
我们通过生成函数成功地将一个数列转化为了一个多项式，从而可以对其进行多项式的运算，如加，减，乘，除，乘法逆，取ln，取exp，快速幂等（
其中使用最多的大概就是乘法计算

怎么做

生成函数大致有三种形式：普通生成函数，指数生成函数和狄利克雷生成函数（理解难度大概是递增的
一、普通生成函数：
首先是一个简单的例题：

三种物品（每种物品之间完全相同），分别有$3,2,3$个，现在取$4$个物品进行组合，问方案总数是多少

用生成函数的思想来看，我们对每个物品构造一个多项式，第$i$项的系数$a_i$表示当前物品选择了$i$件的方案数。那么容易得到这样三个多项式：

$G_1(x) = 1 + x + x^2 + x^3$ $G_2(x) = 1 + x + x^2$ $G_3(x) = 1 + x + x^2 + x^3$

为什么是这样的呢？ —显然数量足够的时候同一种物品选择$i$件的方案数是$1$，所以有$i$件时系数为$1$，不足时系数为$0$，也就没有了。
那么最终的答案就是 $G = G_1(x)*G_2(x)*G_3(x)$ 的第四项的系数。想一想，为什么?
用我们小学二年级就学过的二项式定理可以辅助理解：两个多项式$f$和$g$相乘，结果的第 $k$ 项也就是：

$\sum_{i = 0}^{k}f_ig_{k-i}$

这个$\sum$的过程也就相当在枚举从$f$和$g$两类物品中共选$k$个，其中$f$选$i$个（所以$g$当然选$k-j$个）的方案数，因此求得的多项式的第$k$项系数当然也就是从这两种物品当中共选$k$件的总方案数
所以三个相乘也是同样的道理。
其实这和$dp$当中的背包问题非常相似，实际上背包问题就是在模拟多项式乘法（所以就会出现$ \text{FFT} $优化$dp$这种东西吧）
所以我们把形如

$G(x) = \sum_{i = 0}^{n}a_ix_i$

这种形式的表示一个数列的多项式函数称为普通生成函数

二、指数生成函数
我们发现，普通生成函数可以快速解决组合类问题，那么排列怎么办？
就可以使用指数生成函数来处理这样的问题。
我们把刚刚的例题略作改变：

三种物品（每种物品之间完全相同），分别有$3,2,3$个，现在取$4$个物品进行排列，问方案总数是多少

题目相比之前仅仅把“组合”改成了“排列”，但是对于生成函数来讲，我们当前提到的知识还不足以解决这个问题
这里引入多重集排列数的概念：

设一个集合$S = \{a_1,a_2,\cdots,a_n\}$，物品总数$N = \sum_{i = 1}^n a_i$，那么从集合$S$中选出$N$个进行排列的方案数为：
$\frac{N!}{a_1!a_2!\cdots a_n!}$
可以理解为先任意排列之后再去重

这样我们就有了一个初步的思路：先求出所有的组合方案，再对于每个方案求组合数，再累加起来。
于是我们引入指数型生成函数 ：

形如

$G(x) = \sum_{i = 0}^na_i\frac{x_i}{i!}$

的多项式函数，我们称之为指数型生成函数。
那么我们对于以上问题就可以构造出这样的三个函数：

$G_1(x) = 1 + \frac{x^1}{1} + \frac{x^2}{2!} + \frac{x^3}{3!}$ $G_2(x) = 1 + \frac{x^1}{1} + \frac{x^2}{2!}$ $G_3(x) = 1 + \frac{x^1}{1} + \frac{x^2}{2!} + \frac{x^3}{3!}$

接下来就可以使用~~人列计算机~~算出 $G = G_1 * G_2 * G_3$ 的多项式为：

$G = 1 + 3x + \frac{9}{2} x^2 + \frac{14}{3} x^3 + \frac{35}{12} x^4 + \frac{17}{12} x^5 + \frac{35}{72} x^6 + \frac{8}{72} x^7 + \frac{1}{71} x^8$

此时选出$4$个物品的答案也就容易算出了：
$\frac{35}{12} * 4 ! = 70$
那么为什么这样定义生成函数，乘起来之后就是排列数了呢？因为我们构造时对每个函数乘的$\frac{1}{i!}$就相当于多重集排列数当中的分母了

但是显然我们目前所学的东西还不足以解决更加复杂的问题
那么接下来就是这两类生成函数的一些推广（也就是一些简化运算的方法）：

我们在刚刚的运算中看到了一个常见的柿子： $G(x) = \sum_{i = 0}^nx^i$，那么我们考虑一下化简这个式子,结论是：

$\sum_{i = 0}^\infty x^i = \frac{1}{1-x}$

得到它的过程也很简单，参照无限循环小数转分数的一般过程($S = \frac{xS - S}{x-1}$) 但是我们发现它显然只对 $x \in (-1,1)$ 的情况成立，但是我们知道$x$的取值并不会影响整个柿子的功效，所以我们当然可以假设$x \in (-1,1)$,它在实际上不会影响我们对于这个问题的研究

实际上我们得到的这个柿子被称为这个生成函数的封闭形式，封闭形式是我们在生成函数与原数列的通项公式之间搭起的桥梁，可能这里会产生疑问：封闭形式和通项公式之间有什么关系？实际上我们通过将一般的生成函数的封闭形式转化成几个特殊形式从而得到通项公式，特殊情况有以下几种：

把$x$换为$-x$ : $\sum_{i = 0}^\infty (-1)^i x^i = \frac{1}{1+x} = 1,-1,1,-1,1,-1 \cdots $
把$x$换为$2x$ : $\sum_{i = 0}^\infty 2^i x^i = \frac{1}{1-2x} = 1,2,4,8,16 \cdots $
把$x$换为$x^2$ : $\sum_{i = 0}^\infty x^{2i} = \frac{1}{1-x^2} = 1,0,1,0,1 \cdots $(只有在偶数项有系数1，奇数项无系数)
把分子乘$2$ : $\sum_{i = 0}^\infty 2 x^i = \frac{2}{1-x} = 2，2，2，2，2 \cdots $
把分子乘$x^3$ : $\sum_{i = 0}^\infty x^{i+3} = \frac{x^3}{1-x} = 0,0,0,1,1,1 \cdots $
求个导 : $\sum_{i = 0}^\infty (i+1)x^{i} = \frac{1}{(1-x) ^ 2} = 1,2,3,4,5 \cdots $
(他的推导过程放在下边，实际上并不是很难理解)
首先易得到： $S = \sum_{i = 0}^\infty(i+1)x^i$ 那么就有： $xS = \sum_{i = 0}^\infty(i+1)x^{i+1}$ 我们可以将上式看作上上式所有系数整体右移了一位，那么两式作差后系数相减，全都变成了$1$，也就是： $S - xS = \sum_{i = 0}^{\infty}x^i$ 即： $(1-x) S = \frac{1}{1-x}$ $S = \frac{1}{(1-x)^2}$ 推毕
再求一次： $\sum_{i = 0}^\infty (i+1)(i+2)x^{i} = \frac{2}{(1-x) ^ 3} = 2,6,12,20 \cdots $
至于这玩意怎么推$\cdots$我自己本来不会，所以我去问了机房巨佬，巨佬秒了它之后几句话给我讲明白了，过程如下： $S = \sum_{i = 0}^{\infty}(i+1)(i+2)x^i$ $xS = \sum_{i = 0}^{\infty}(i+1)(i+2)x^{i+1}$ 同样是系数右移一位，所以就有： $\begin{matrix} & & 0 & 1 & 2\\ & S & 1*2x^0 & 2*3x^1 & 3*4x^2\\ & xS & - & 1*2x^1 & 2*3x^2 \end{matrix}$ 上下相减可得： $S - xS = (1 * 2) + (2 * 2) x + (3 * 2) x^2 + \cdots$ 显然可以提出一个$2$ ： $(1-x) S = 2 * (\sum_{i = 0}^\infty (i+1)x^i)$ 而后面的$\sum_{i = 0}^\infty (i+1)x^i$我们刚刚已经推过了，是$\frac{1}{(1-x)^2}$,也就是说： $(1-x) S = \frac{2}{(1-x)^2}$ $S = \frac{2}{(1-x)^3}$ 推毕(sto Jekyll_Y orz)
那么有了生成函数和封闭形式,如何求数列的通项公式呢？

有一个常用的定理： 广义二项式定理
全部情况放一个链接广义二项式定理，这里只摆出一个常用的：

$\frac{1}{(1-x)^n} = \sum_{k = 0} ^ \infty C_{n+k-1}^{k-1}x^k$

举一个经典例子来应用一下：求斐波那契数列的通项公式（我猜很多人想干这个事已经很久了）：
我们设斐波那契数列为数列$A$,其中第$0$项为$1$，由斐波那契数列的递推性质可知我们用原数列减去右移一位后的数列再减去右移两位后的数列，应当可以得到一个项很少的多项式（因为后边的全消了,实际上得到的只有1），算一下也就是：

$A - xA - x^2A = 1$

那么生成函数也就是：

$A = \frac{1}{1-x-x^2}$

可惜到这里仅仅迈出了第一步——生成函数不能直接告诉我们每一项的系数。那么按照前边的思想，我们应当尝试把这个公式向已知的特殊形式转化：
我们已知 $\frac{1}{1-kx} = \sum_{i = 0}^\infty k^i x^i = 1,k,k^2,k^3, \cdots $那么显然可以向这个方向靠拢，于是我们尝试对$1-x-x^2$因式分解（说白了就是解一元二次方程）

设$1-x-x^2 = (1-x_1)(1-x_2)$
可以解得：

$x_1 = \frac{1+\sqrt{5} }{2},x_2 = \frac{1-\sqrt{5}}{2}$

其中$x_1,x_2$满足轮换对称（说白了就是可以互换）
那么我们可以设$\frac{1}{1-x-x^2} = \frac{a}{1-x_1x} + \frac{b}{1-x_2x} $，然后去一下分母，也就是解这个方程：

$(a+b-1) - x(ax_1 + bx_2) = 0$

对任意的$x$要求方程恒成立$\cdots $那么问题解决了：

$\begin{cases} a+b=1 \\ ax_1 + bx_2 = 0 \end{cases}$

随便解一解也就是

$\begin{cases} a=\frac{1}{\sqrt{5}}x_1 \\ b=-\frac{1}{\sqrt{5}}x_1 \end{cases}$

代回可得：

$A = \frac{x_1}{\sqrt{5}}\frac{1}{1 - x_1x} - \frac{x_2}{\sqrt{5}}\frac{1}{1 - x_2x}$

所以通项公式就有了：

$A_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1})$

至此，我们已经能用生成函数的知识解决斐波那契数列通项公式的问题了

下面我们来说一说指数类生成函数的推广：

结论是：

$e^x = \sum_{i = 0}^{\infty}\frac{x^i}{i!}$

至于证明$\cdots$将$e^x$麦克劳林展开（x_0 = 0处的泰勒展开）一下就行

排列与圆排列

（坑，以后填）

三、迪利克雷生成函数
（坑，以后填）