- 一.一些基础知识
费马定理：若 (f) 在 (x_0) 某邻域有定义，且在 (x_0) 处可导，那么如果 (x_0) 为 (f) 极值点则 (f(x_0)=0)
罗尔中值定理：若 (f) 在 ([a,b]) 连续且在 ((a,b)) 可导且 (f(a)=f(b)),那么存在一个 (xin (a,b))，使得 (f(x)=0)
洛必达法则：若 (f,g) 满足
1.(limlimits_{x ightarrow x_0}f(x)=limlimits_{x ightarrow x_0}g(x)=0)
2.在 (x) 的某空心邻域 (U^o(x_0)) 中 (f，g) 均可导且 (g'(x) eq 0)
3.(limlimits_{x ightarrow x_0}frac{f(x)}{g(x)}=A)
则 (limlimits_{x ightarrow x_0}frac{f(x)}{g(x)}=limlimits_{x ightarrow x_0}frac{f'(x)}{g'(x)}=A)
- 二.经典问题
普通型生成函数
- 1.(Fibonacci) 数列的生成函数
考虑 (a_i=a_{i-1}+a_{i-2})，若 (G(x)) 为 (Fibonacci) 数列的生成函数
那么$$egin{aligned}A&=a_0+a_1x+a_2x^2+...xA&=0+a_0x+a_1x^2+...x^2A&=0+0+a_0x^2+...end{aligned}$$
则 (A-xA-x^2A=1)
所以 (A=frac{1}{1-x-x^2})
- 2.(Catlan) 数的生成函数
我们知道 (c_n=sumlimits_{i=0}^{n-1}c_ic_{n-i-1})，若 (C(x)) 为 (Catlan) 数列的生成函数
则 (C^2(x)=sumlimits_{i=0}^{infty}c_{i+1}x^i)，平移一下得到 (xC^2(x)=sumlimits_{i=1}^{infty}c_ix^i)
所以 (C(x)=1+xC^2(x))，即 (C(x)=frac{1-sqrt{1-4x}}{2x})
泰勒展开一下可以得到 (Catlan) 通数项公式 (c_i=frac{1}{i+1}inom{2i}{i})
指数型生成函数
排列的生成函数 (hat{P}(x)=frac{1}{1-x})
环排列生成函数 (hat{H}(x)=ln(frac{1}{1-x}))
我们发现 (hat{P}(x)=e^{hat{H}(x)})，根据环排列可以组成排列推导可发现组成关系均满足这一柿子
错排生成函数 (hat{C}(x)=e^{hat{H}(x)-x}=frac{e^{-x}}{1-x})，根据在排列中减去大小为1的环排列得到
n个点有标号无向连通图生成函数，根据n个点有标号无向图生成函数 (hat{W}(x)=sumlimits_{i=0}^{infty}2^{inom{i}{2}}x^i) 得到 (hat{L}(x)=ln(hat{W}(x)))