参考资料：OI-Wiki、APJ's pdf、学长的课件
生成函数 \(\text{GF(Generating Function)}\)
定义
定义一个数列 \(\{a_n\}\) 的生成函数（或母函数）\(F(x)\) 为：
\[F(x)=\sum_{i\ge 0}a_ix^i \]这是个无限项的形式幂级数，然而我们实际上只关心有限项。
\(x\) 并没有实际意义，只是占位符。这种情况在最初的多项式卷积中就已经见到过了。
将一般的卷积写成生成函数的好处在于方便进一步推导。
简单数列的生成函数
- \(\{1,1,1,1,1,\cdots\}\)
- \(\{0,1,2,4,8,\cdots\}\)
- \(\{1,0,1,0,1,\cdots\}\)
- \(\{0,1,0,1,0,\cdots\}\)
由于 \(x\) 作为占位符，无穷项求和时是否收敛并不重要，最多只关心 \(x=0\) 时的意义。
斐波那契数列生成函数
对于 \(n\ge 2\)，有：
\[f_n=f_{n-1}+f_{n-2} \]于是可以写成：
\[F(x)=xF(x)+x^2F(x) \]然而边界值不能确定，只需要补足 \([x^1]F(x)=1\) 即可，于是：
\[F(x)=xF(x)+x^2F(x)+x \]整理一下变成：
\[F(x)=\dfrac{x}{1-x-x^2} \]设 \(\dfrac{x}{1-x-x^2}=\dfrac{A}{1-ax}+\dfrac{B}{1-bx}\)
根据上面的举例，可以知道左右两个分式都能写成等比的生成函数，于是：
\[[x^n]F(x)=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right] \]这个就是斐波那契数列的通项公式了。
普通生成函数 \(\text{OGF(Original Generating Function)}\)
用于无标号计数。
形式
\[F(x)=\sum_{i\ge 0} a_ix^i \]当 \(a_i=k^i\) 时，封闭形式：
\[F(x)=\dfrac{1}{1-kx} \]一个简单的例子
有红黄蓝三种球各 \(m\) 个，从中共选出 \(n\) 个，求方案数。
构造生成函数 \(G(x)=1+x+x^2+\cdots+x^m\)，三种球的选择实际上就是乘积贡献到指数和的位置，也就是卷积，于是可以写成：
\[f_{n}=\sum_{i,j,k}g_i\times g_j\times g_k[i+j+k=n] \]生成函数的形式就是：
\[F=G*G*G=G^3 \]范德蒙德卷积
\[\dbinom{n+m}{k}=\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i} \]左侧是 \([x^k](1+x)^{n+m}\)，右侧是 \([x^i](1+x)^n\times [x^{k-i}](1+x)^m\)
这样一看好像很显然了。
一道题
CodeForces-438E The Child and Binary Tree
设 \(g_i\) 为该权值是否在集合中，\(f_i\) 为权值和为 \(i\) 的方案数，写出转移式子：
\[f_n=\sum_{i=0}^{n} g_i\sum_{j=0}^{n-i} f_{j}\times f_{n-i-j} \]就是三个函数卷一下，但是重要的地方在于初始值 \(f_0=1\)，于是生成函数应该写成：
\[F=F^2G+1 \]解一下：
\[F=\dfrac{1\pm\sqrt{1-4G}}{2G} \]分子有理化：
\[F=\dfrac{2}{1\mp \sqrt{1-4G}} \]\(G=0\) 时加号有意义，因此是：
\[F=\dfrac{2}{1+\sqrt{1-4G}} \]卡特兰数生成函数
卡特兰数的一个递推式：
\[C_n=\sum_{i=0}^{n-1}C_i\times C_{n-i-1} \]也就是：
\[C=xC^2+1 \]解完和上一题差不多，是：
\[C=\dfrac{2}{1+\sqrt{1-4x}} \]据说再解就出通项了。
指数生成函数 \(\text{EGF(Exponential Generating Funtion)}\)
用于有标号计数。
形式
\[F(x)=\sum_{i\ge 0}\dfrac{a_ix^i}{i!} \]\(a_i=1\) 的特殊情况：
\[F(x)=\sum_{i\ge 0}\dfrac{x^i}{i!}=e^x \]因此 \(a_i=k^i\) 时：
\[F(x)=e^{kx} \]一个简单的例子
还是红黄蓝三种球，只不过这次是要出一个排列。
\[f_n=\sum_{i,j,k} \dbinom{n}{i,j,k}g_i\times g_j\times g_k[i+j+k=n] \]拆开组合数很神奇的是：
\[\dfrac{f_n}{n!}=\sum_{i,j,k} \dfrac{g_i}{i!}\times \dfrac{g_j}{j!}\times \dfrac{g_k}{k!}[i+j+k=n] \]长得很像，同样也是：
\[F=G^3 \]一道题
常规容斥做法不多赘述。
设 \(F(x)\) 为无向连通图个数的生成函数，那么 \(F(x)\) 卷多次得到：
\[G(x)=\sum_{i\ge 0}\dfrac{F^i(x)x^i}{i!} \]除以一个 \(i!\) 是因为连通块没有顺序区别，而 \(F(x)\) 卷积是有顺序区别的。
这个东西长得和封闭形式的 \(k^i\) 很像，也就是：
\[G(x)=\exp F(x) \]而 \(G(x)=\sum_{i\ge 0} 2^{\tbinom{i}{2}}x^i\) 是已知的，\(\ln G(x)=F(x)\) 回来即可。
多项式 \(\text{exp}\) 与多项式 \(\ln\) 的组合意义
通过上面的题实际上已经得出了，一个整体方案数生成函数的 \(\exp\) 就是任意一个独立整体方案数生成函数（例如上面的连通图与无限制），而 \(\ln\) 的组合意义就是由 \(\exp\) 反向得到的。
标签：函数,多项式,sum,笔记,生成,学习,ge,dfrac,times From： https://www.cnblogs.com/SoyTony/p/Learning_Notes_about_Polynomial_4.html