设\(\alpha\)是实数，对于所有满足\(0\leq |x| <|y|\)的\(x\)和\(y\)，有
其中
（假设下式中的所有导数均是有意义的）
对于某个函数\(f(x)\),我们可以取一个使其有\(n\)阶导的\(x_0\)，并利用\((x-x_0)\)的\(n\)次多项式来逼近\(f(x)\).此时下式成立：
其中\(f^{(n)}(x)\)为\(f(x)\)的\(n\)阶导数，\(R_n(x)\)表示余项（事实上由于生成函数都是形式幂级数，我们不需要考虑其在何处收敛，更重要的是一般题目只会要求保留前\(n\)项，所以OI里根本不关心\(R_n(x)\)长啥样.）
当\(x_0=0\)时，\(f(x)\)的泰勒展开即为麦克劳林级数，即
对于给定的数列\(A\)，定义其一般生成函数(Ordinary Generating Function,简称OGF)\(A(x)\)为
例子：
数列\(<1,1,1,\cdots>\)的生成函数为\(1+x+x^2+\cdots\).
数列\(<0,1,2,\cdots>\)的生成函数为\(0+x+2x^2+\cdots\).
对两个生成函数\(F(x),G(x)\).
根据上述运算法则，我们可以找到一些有着特殊性质的数列的OGF.
考虑数列\(<1,1,1,1,1>\)的OGF，它是\(1+x+x^2+x^3+x^4\).
发现它有点像等比数列求和的形式，那么能不能把它按照等比数列求和公式写成\(\frac{1-x^5}{1-x}\)呢？
虽然看起来这时\(x=1\)时这个函数是无意义的，但是由于生成函数本质上是形式幂级数，所以我们并不关心它在何处收敛。我们只考虑这个函数的麦克劳林级数即可。
将上面的结论推广可以得到数列\(<1,1,1,\cdots>\)的OGF为\(\frac{1}{1-x}\).
继续推广上面的结论，可以得到数列\(<1,a,a^2,\cdots>\)的OGF为\(\frac{1}{1-ax}\).
考虑一下\((\frac{1}{1-x})^2\)是什么，它可以看成是两个\(1+x+x^2+\cdots\)的乘积，那么新函数的第\(i\)项的系数等价于将\(i\)拆成两个非负整数的和的方案数，也就是说新函数是数列\(<1,2,3,\cdots>\)的生成函数。
继续推广下去，\(\frac{1}{(1-x)^m}\)可以看成\(m\)个\(1+x+x^2+\cdots\)的乘积，故\(x^i\)的系数为将\(i\)拆分为\(m\)个非负整数之和，也就是\(\dbinom{i+m-1}{i}\).再把\(x\)代换为\(ax\)，就有了这个式子：
然后拿一些东西带进去就会有一些好玩的东西：
最后还有一个\(<1,\frac{1}{2},\frac{1}{3},\cdots>\),它的生成函数是\(-\ln(1-x)\),证明的话考虑将后面那个Taylor展开即可。
求数列\(<0,1,4,\cdots,n^2,\cdots>\)的生成函数
令所求的生成函数为\(F(x)\), 则有
最后可以得到
已知Fibonacci数列的递推式为：
求数列\(f_n\)的生成函数\(F(x)\).
解得\(F(x)=\frac{1}{1-x-x^2}\).
看起来我们的确完成了认为，但是这个封闭形式除了长的短以外毫无作用。
注意到那些形如\(\frac{1}{1-ax}\)的生成函数我们是能够很好的展开的，于是考虑将这个封闭形式写成若干个乘积。
令\(\phi=\frac{1+\sqrt 5}{2},\hat{\phi}=\frac{1-\sqrt5}{2}\),则分母有\(1-x-x^2=(1-\phi x)(1-\hat{\phi} x)\)，之后我们假设\(F(x)=\frac{A}{1-\phi x}+\frac{B}{1-\hat{\phi}x}\)，最终解得\(F(x)=\frac{1}{\sqrt 5}(\frac{1}{1-\phi x}-\frac{1}{1-\hat{\phi} x})=\frac{1}{\sqrt 5}\sum_{i\geq 0}(\phi^i-\hat{\phi}^i)x^i\).
生成函数在求解选取某些物品的方案数时有一些神奇的效果。
例题：有\(A.B,C,D\)四种物品，假设每种都有无限个，现在要求恰好拿出\(n\)个，其中\(A\)必须拿偶数个，\(B\)必须拿\(5\)的倍数个，\(C\)至多能拿\(4\)个，\(D\)至多能拿\(1\)个，求方案数。
解：分别记拿\(A,B,C,D\)四种物品拿\(n\)个的方案数的生成函数为\(A(x),B(x),C(x),D(x)\).那么显然有：
记最终答案的生成函数为\(F(x)\)，根据组合意义发现有\(F(x)=A(x)B(x)C(x)D(x)=\frac{1}{(1-x)^2}=1+2x+3x^2+\cdots\).也就是\([x^n]F(x)=n+1\)，故最终的答案就是\(n+1\).
考虑一下上面那个数数题，我们认为\(F(x)\)是简单的四个生成函数相乘的结果，是因为在这里我们认为顺序不影响结果，我们只关心每一类物品选了多少个。举个例子，假设某个\(n=3\)的方案依次选了2个\(A\)物品和1个\(B\)物品,那么无论\(B\)在两个\(A\)之前还是之后都是同一种方案。那么假设题目开始考虑这一种情况了呢？
考虑一种只有\(2\)个物品且无限制的情况：假设我们当前选了\(n\)个\(A\)物品和\(m\)和\(B\)物品，那么最终是有\(n+m\)个物品的，考虑把这看成一个长\(n+m\)的序列，则有\(n\)个位置上是物品\(A\)，所以在两种物品的方案数相乘的同时还有一个组合数的贡献。具体的，我们记选A物品和选B物品的方案数分别是\(f_i,g_i\)，最终答案的\(h_i\)，则有
我们发现，如果能把\(i!\)也看成是\(x^i\)的一部分的话，那么它们的生成函数的乘法依然和最开始的OGF是一致的，这就引出了指数生成函数(Exponential Generating Function,简称EGF).
对于给定的数列\(A\)，定义其指数型生成函数\(A(x)\)为：
记\(F(x),G(x)\)分别是数列\(f_i,g_i\)的EGF.
其中\(n^{\underline{m}}=n(n-1)\cdots(n-m+1)\).
注意到，由于在OI中我们存储EGF时一般存的都是\(\frac{f_n}{n!}\),所以要想实现\(f_n\)的左移和右移需要借助求导和积分。
注意数列\(f_n\)的EGF和数列\(\frac{f_n}{n!}\)是等价的。
不要忘记EGF是考虑不同种物品之间的顺序的，相对应的，OGF并不考虑。
例：用红、白、蓝三种颜色给\(1\times n\)的格子染色，要求红色格子的数目是偶数，且至少有一个格子是蓝色的方案数\(f_n\).
解：记\(f_n\)的EGF为\(F(x)\).仿照OGF的例题，我们将三种颜色的方案数的生成函数乘起来。
故最终有
考虑这样的问题：我们需要数集合\(S\)中元素的数量，但是集合\(S\)是由集合\(A\)中的元素拼接而成的。假设我们已知集合\(A\)中元素的生成函数，那么集合\(S\)的生成函数为（下式的\(A,S\)均表示函数）
例：求\(n\)个点的无向有标号连通图的数量\(f_n\), 要求无重边无自环。
解：记\(n\)个点的无向图的数量为\(g_n\). 由于\(n\)个点的无向图中最多有\(\dbinom{n}{2}\)条边，每条边的存在与否都会影响到方案，故有：
分别记\(f_n,g_n\)的生成函数为\(F(x),G(x)\)，由于无向图可以看成是若干个无向连通图拼在一起形成的，故：
两边同时取\(\ln\)
至于多项式如何取\(\ln\), 并不是本文的重点。可以自行上网百度
原文：https://www.cnblogs.com/encodetalker/p/12657259.html