1.多项式基础
约定： (F[n] 或 [x^n]F(x)) 表示为多项式 (F(x)) 第 (n) 项的系数。
(1)多项式卷积
(F(x) * G(x) = displaystylesum_{i=1}^{n}sum_{j=1}^{n} F[i]G[j]x^{i+j})
同理 ((F*G)[n] = displaystylesum_{i=1}^{n} F[i]G[n-i])
(2)多项式复合
(F(G[x]) = displaystylesum_{i=1}^{n} F[i]G(x)^i)
可以理解为整体替换的形式。
当 (F(G(x)) = x) 时，则称 (F,G) 互为复合逆。
(3)泰勒展开
设 (F^{(n)}(x)) 表示 (F(x)) 的 (n) 阶导数，则有 (F(x)) 在 (x_0) 处的泰勒展开为 ：
(F(x) = displaystylesum_{i=0} {F^{(i)}(x_0)over i!} (x-x_0)^i)
(4) 麦克劳林级数
取 (F(x)) 在 (0) 处的泰勒展开，则有 (F(x) = displaystylesum_{i=0} {F^{(i)}(0)over i!} x^i) 这是一个幂级数的形式。
根据这个式子，我们用卷积来定义一些东西。
一个经典的例子就是 (e^x = displaystylesum_{i=0}{x^iover i!})。
(5) 牛顿二项式定理
下文中 (dbinom{n}{k} = {n(n-1)(n-2)...(n-k)over k!})
((x+y)^n = displaystylesum_{i=0}^{n} dbinom{n}{i}x^iy^{n-i})
当 (n) 为正数的时候 ((x+y)^{n} = displaystylesum_{i=0}^{n} C_{n}^{i} x^iy^{n-i})
当 (x) 为负数的时候 ((1+x)^n = displaystylesum_{i=0}^{n} C_{n-i+1}^{i} x^i)
2.生成函数的引入
对于一个无穷数列 (F)，定义其生成函数为：
(displaystylesum_{i=0} F[i] x^i = F[0]x^0 + F[1]x^1 + F[2]x^2 ....)
形式化来说就是：数列的每个数分别附上代数对象 (x) 的幂，从而得到了一个幂级数 （你也可以暂且理解为多项式）
比如数列 (F=<1,1,1,1....1>) ,他的生成函数为 (displaystylesum_{i=0}x^i = 1 + x^1+x^2+x^3....)
作为生成函数 (F(x))， (x) 的取值我们是不关心的，我们只关心的是 (F[n]) 的值，同理函数的值也是没有意义的。
我们观察一下上面的 (F(x)) ,不难发现：
(F[x] = 1+x^1+x^2+x^3+x^4+x^5+....)
(xF[x] = x^1+x^2+x^3+x^4+x^5+...)
两式相减可得： ((1-x)F(x) = 1) 。
可以得到 (F(x) = {1over 1-x})
我们称 (1over 1-x) 为 (F(x)) 的封闭形式。
形式化来说就是：对于无穷数列的求和我们不能很好的表示出来。相对简洁的形式就叫做封闭形式。
同理，我们还可以得到以下封闭形式：
- (1+x+x^2+x^3 +... = {1over 1-x})
- (1+ax+ax^2+ax^3+ax^4+... = {1over 1-ax})
- (displaystylesum_{i=0} x^{ik} = {1over 1-x^k})
- (displaystylesum_{i=0} cx^{ik} = {1over 1-cx^k})
例题： bzoj3028 食物
我们把每种食物的生成函数写出来，相乘即为选取食物方案数的生成函数 (F(x))。
汉堡： (1+x^2+x^4+x^6+...) , 封闭形式为 ({1over 1-x^2})
可乐： (1+x)
鸡腿： (1+x+x^2)
蜜桃多： (x+x^3+x^5+...), 封闭形式为 (xover 1-x^2)
鸡块： (1+x^4+x^8+... = {1over 1-x^4})
包子： (1+x^1+x^2+x^3 = {1-x^4over 1-x})
土豆片炒肉： (1+x)
面包： (1+x^3+x^6+... . = {1over 1-x^3})
相乘起来可得： (F[x] = {xover (1-x)^4})， 根据牛顿二项式定理展开可得： (F(x) = xdisplaystylesum_{i=0}C_{i+3}^i x^i = xsum_{i=0}c_{i+3}^3 x^i)
所以取 (n) 个食物的方案数为 (F[n] = C_{i+2}^{3}) ，利用卢卡斯定理求组合数即可。
3.一些生成函数的推导
主要是利用生成函数来解决一些递推问题。
斐波那契数列的生成函数
递推定义式： (F[0] = 0,F[1] = 1. F[i] = F[i-1] + F[i-2] (i>1))
把他写成生成函数的形式： (F(x) = displaystylesum_{i=0} F[i]x^i), 不能看出什么东西来。
考虑利用适当的错位让 $F(x) $ 表示他自己：
(F(x) = F[0] + F[1]x^1+F[2] x^2+F[3]x^3....)
(xF(x) = F[0]x^1+F[1]x^2+F[2]x^3.... = displaystylesum_{i=1}F[i-1]x^i)
(x^2F(x) = F[0]x^2+F[1]x^3+F[2]x^4... = displaystylesum_{i=2}F[i-2]x^i)
(xF(x)+x^2F(x) = displaystylesum_{i=1}F[i-1]x^i+sum_{i=2}F[i-2]x^i)
(xF(x)+x^2F(x) = F[0] + displaystylesum_{i=2}F[i]x^i)
由此可得： (xF(x)+x^2F(x) = F(x)-x)
解得： (F(x) = {xover 1-x-x^2})
这个虽然是个封闭形式，但是并不能给我们关于 (F[n]) 的信息, 我们现在想办法把他转化为无穷级数的形式。
考虑解一个待定系数方程： ({Aover 1-ax} + {Bover 1-bx} = {xover 1-x-x^2})
展开可得： ({{A-Abx} + {B - Bax}over (1-ax)(1-bx)} = {xover 1-x-x^2})
可得： (egin{cases} A+B = 0\Ab-Ba = 0\ab = -1\a+b = 1end{cases})
解得：(egin{cases} A={1over sqrt{5}}\B = {-{1over {sqrt5}}}\a = {(1+sqrt{5})over 2}\b = {1-sqrt{5}over 2}end{cases})
然后我们就可以得到斐波那契数列的通项公式： (F(x) = displaystylesum_{n=0} x^n{1over sqrt{5}} left(left({(1+sqrt{5})over 2} ight)^n - left({{1-sqrt{5}}over 2} ight)^n ight))
4.普通生成函数和指数生成函数
OGF（普通生成函数）
设数列 (F[n]), 其 (OGF) 为 (F(x) = displaystylesum_{i=0}F[i]x^i) 。
考虑两个序列 (a,b) 的普通生成函数，分别为 (F(x),G(x)),则有：
(F(x)+G(x) = displaystylesum_{i} (a_i+b_i)x^i)
所以 (F(x)+G(x)) 是序列 (<a_n+b_n>) 的 ( ext{OGF})。
乘法运算(卷积)则有：
(F(x)G(x) = displaystylesum_{i} x^isum_{j=0}^{i}a_ib_{i-j})
所以 (F(x)G(x)) 是序列 (<displaystylesum_{i=0}^{n}a_ib_{n-i}>) 的 ( ext{OGF})
John 得到了 (n) 罐糖果。不同的糖果罐，糖果的种类不同（即同一个糖果罐里的糖果种类是相同的，不同的糖果罐里的糖果的种类是不同的）。第 (i) 个糖果罐里有 (m_{i}) 个糖果。John 决定吃掉一些糖果，他想吃掉至少 (a) 个糖果，但不超过 (b) 个。问题是 John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢？
生成函数入门题。
首先我们把每个糖果的生成函数写出来即： (f(x) = x^0+x^1+x^2 ..... + x^m).
(ecause xf(x) = x^1+x^2+....x^{m+1})
( herefore f(x)-xf(x) = 1-x^{m+1})
( herefore f(x) = {1-x^{m+1}over{1-x}})
把每个糖果的生成函数乘起来： (displaystyle{prod_{i=0}^{n} (1-x^{m_i+1})}over(1-x)^n)
分子展开之后最多有 (2^n) ，暴力展开即可。
分母由牛顿二项式定理可得： ((1-x)^{-n} = displaystylesum_{k=0}^{infty}C_{n+k-1}^{k}x^k)
考虑假如说当前分子枚举到 (x^{k}) ,那么分母对当前答案的贡献即为 (displaystylesum_{i=a-k}^{b-k} C_{n+i-1}^{i}) .
由 杨辉三角可得, (displaystylesum_{i=a-k}^{b-k} C_{n+i-1}^{i} = C_{n+b-k}^{b-k} - C_{n+a-k-1}^{a-k-1})
可以模数不是质数，没有逆元怎么办？
(displaystyle ecause C_{n+b-k}^{b-k} = {(n+b-k)!over{n!(b-k)!}})
(displaystyle herefore C_{n+b-k}^{b-k} = {(n+b-k)(n+b-k-1)....(b-k+1)over n!})
因为 $n! $ 很小，所以可以在算分子的时候把模数变为 (n! imes p) ,最后在除以 (n!) 即可。
EGF 指数生成函数
序列 (a) 的指数生成函数 ( ext{EGF}) 定义为：
(F(x) = displaystylesum_{i=0}a_i{x^iover i!})
指数生成函数的加法和普通生成函数是一样的。
乘法运算（卷积）：
(F(x)G(x) = displaystylesum_{i=0}^{infty} a_i{x^iover i!} sum_{j=0}^{infty}b_j{x^jover j!})
(F(x)G(x) = displaystylesum_{i=0}^{infty}x^isum_{j=0}^{i} a_jb_{i-j}{1over j!(i-j)!})
(F(x)G(x) = displaystylesum_{i=0}^{infty}{x^iover i!}sum_{j=0}^{i}a_jb_{i-j}{i!over j!(i-j)!})
(F(x)G(x) = displaystylesum_{i=0}^{infty}{x^iover i!} sum_{j=i}^{n}{ichoose j}a_jb_{i-j})
所以 (F(x)G(x)) 是 (<displaystylesum_{i=0}^{n}{nchoose i}a_ib_{n-i}>) 的 ( ext{EGF}) 。
常见的封闭形式：
- ({1,1,1,1,.....} Rightarrow e^x)
- ({1,-1,1,-1,1,....}Rightarrow e^{-x})
- ({1,c,c^2,c^3.....} Rightarrow e^{cx})
- ({1,0,1,0,1,0.....} Rightarrow {e^x+e^{-x}over 2})
exp 的组合意义
我们观察 ( ext{exp} F(x) = displaystylesum_{i} {F(x)^iover i!})
如果把 (F(x)) 看做单个元素的 ( ext{EGF}), 那么 ( ext{exp} F(x)) 就描述了这些元素组成的有标号的集合。
举几个例子：
- 如果 (n) 个点带标号的生成树的 ( ext{EGF}) 为 (F(x))， 那么 (n) 个点带标号的森林的 ( ext{EGF}) 即为 ( ext{exp} F(x)) ,直观理解为将 (n) 个点分为若干个集合，每一个集合构成一棵树的方案数之积。
- 如果 (n) 个点带标号的无向连通图的 ( ext{EGF}) 为 (F(x)), 那么 (n) 个点带标号的无向图的 ( ext{EGF}) 即为 ( ext{exp} F(x)) 。直观理解为把 (n) 个点分为若干个集合，每一个集合构成无向连通图的方案数之积。