生成函数1

生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

其用来计算组合数中诸如选择某一数量方案数的一种强有力的工具

加法生成函数

也算常生成函数啦

对于一个生成函数，将其定义为形式幂级数

如：
$$F(x)=\sum _n{a}_n{x}^n$$
其中a可以是有穷数列，也可以是一个无穷数列

我们通常这么写
$$\begin{gathered} a=<1,2,3>\to 1+2x+3x^2 \\ a=<1,1,1,1,1>\to 1+x+x^2+x^3+x^4 \\ a=<1,1,\mathrm{1....}>\to \sum _{n\ge 0}{x}^n \end{gathered}$$
后面的形式就是其生成函数

其实也就是：$(1+x{)}^n$，展开利用二项式定理啊，即$1+C_n^{1}x+C_n^2{x}^2+\cdots +c_n^n{x}^n$

比如我们在这一堆中选k个，那么方案数就是$x^k$的系数

是不是非常神奇！！！

那么我们现在考虑如下一个问题

两种物体a,b都有无限个，求取出n个的方案数

发现这个东西有两个数列，那么我们就可以根据这两个数列分别构造他们的母函数:$A_n,B_n$

怎么把他们搓在一起，解决一共选n个的问题

这个东西就叫做：生成函数卷积

就是$H_n=A_0{B}_n+A_1{B}_{n-1}...A_n{B}_0$

下面我们来讨论一下母函数的性质吧

1. 放缩 $<c{g}_0,c{g}_1,c{g}_2,,...>\Rightarrow cG(x)=c{g}_0,c{g}_1,...$
2. 加减 $<f_0\pm g_0,f_1\pm g_1,...>\Rightarrow F(x)\pm G(x)=f_0\pm g_0+f_1\pm g_1....$
3. 右移 $<0,0,...0,g_0,g_1,...>$，前面k个0，$\Rightarrow x^{k}G(x)$
4. 求导 $G^{\prime }(x)=g_1+2g_{2}x+3g_3{x}^2...\Rightarrow <g_1,2g_2,3g_3,..>$其实就是n-1的方案数

这些性质都非常重要且常用不过这玩意本来也不怎么考就对了