初识生成函数

# 泰勒展开-皮亚诺余项:
*本文中$f^{(i)}都指f的i阶导数$
$$
f(x) = (\sum^\infty_{i = 0}\frac{f^{(i)}(x_0)(x-x_0)^i}{i!})+o[(x-x_0)^{\infty}], o[(x-x_0)^{\infty}]\approx0
$$

$$
f(x) = (\sum^\infty_{i = 0}\frac{f^{(i)}(x_0)(x-x_0)^i}{i!})
$$

### 推论1：$\frac{1}{1-x} = \sum^{\infty}_{i=0}x^i$

##### 对$f(x_0)=\frac{1}{1-x_0}$求 $i$ 阶导：

$$
f^{(i)}(x_0)=\frac{i!}{(1-x_0)^{i+1}}
$$

##### 由泰勒展开可推知：

$$
f(x)= \frac{1}{1-x} = (\sum^\infty_{i = 0}\frac{\frac{i!}{(1-x_0)^{i+1}}(x-x_0)^i}{i!})
$$

$$
令x_0=0, f(x)=(\sum^{\infty}_{i=0}\frac{x^i}{(1-0)^{i+1}})
$$

$$
\frac{1}{1-x} = \sum^{\infty}_{i=0}x^i
$$

### 推论2：$e^x=\sum^\infty_{i = 0}\frac{x^i}{i!}$

##### 已知对于任意$i\in N$ ：$f(x)=e^x, f^{(i)}(x) = e^x$

##### 由泰勒展开推知：

$$
f(x)= e^x = \sum^\infty_{i = 0}\frac{e^{x0}(x-x_0)^i}{i!}
$$

$$
令x_0=0, f(x)=\sum^\infty_{i = 0}\frac{x^i}{i!}
$$

### 推论3：$\frac{k}{1-x} = \sum^{\infty}_{i=0}k\cdot x^i$

##### 对于$\frac{k}{1-x}$求$i$阶导：

$$
f^{(i)}(x_0)=\frac{k\cdot i!}{(1-x_0)^{i+1}}
$$

##### 同推论1可推知：

$$
\frac{k}{1-x} = \sum^{\infty}_{i=0}k\cdot x^i
$$

### 推论4：对于函数$f(x)=\sum^{\infty}_{i=0} k_i\cdot x^i$ 若对$b\in N$有$f^{(b+1)}(x_0)=\sum^{b}_{i=0}f^{(b)}(x_0)$ 那么$f^{'}(x)=\sum^{\infty}_{i=0}(\sum^{i}_{j=0}k_i)x^i$ ，即$f^{'}(x)$的系数是$f(x)$系数的前缀和

##### 令$x_0=0$由已知：

$$
f(x) = (\sum^\infty_{i = 0}\frac{f^{(i)}(0)x^i}{i!})
$$

##### 则：

$$
f^{'}(x)=f^{(1)}(x) = (\sum^\infty_{i = 0}\frac{f^{(i+1)}(0)x^i}{i!})
$$

##### 对于每一项的系数：

$$
f^{'}(x) : k_i=\frac{f^{(i+1)}(0)}{i!}，f(x) : k^{'}_i=\frac{f^{i}(0)}{i!}
$$

$$
因为有f^{(b+1)}(x_0)=\sum^{b}_{i=0}f^{(b)}(x_0)，k_i=\sum^{b}_{i=0}k^{'}_{i}
$$

### 推论5：$\frac{1+x}{(1-x)^2}=\sum^{\infty}_{i=0}(2i+1)x^i$

$$
已知对于函数:f(x)=\sum^{\infty}_{i=0}x^i=\frac{1}{1-x}和g(x)=\sum^{\infty}_{i=1}x^i=\frac{x}{1-x}，有f(x)=x\cdot g(x)
$$

$$
那么可推知：h(x)=f(x)+g(x)=\frac{1}{1-x}+\frac{x}{1-x}=\frac{1+x}{1-x}且h(x)=(\sum^{\infty}_{i=1}2\cdot x^i) + 1
$$

$$
有：h(x)=\frac{1+x}{1-x}=(\sum^{\infty}_{i=1}2\cdot x^i) + 1
$$

$$
由推论4可知：对函数求导有：\frac{1+x}{(1-x)^2}=[\sum^{\infty}_{i=0}(2i+1)\cdot x^i]+1
$$

### 上述公式推理可能不太好理解，我们看泰勒展开后的系数数列：

$\frac{1+x}{(1-x)^2}:1,3,5,7,9,11,13,15,17,19,21,23$

$\frac{1+x}{1-x}:1,2,2,2,2,2,2,2,2,2,2,2,2,2,2$

### 根据推论4，两个函数满足推论4的性质，所以下式为上式前向差分

# 指数生成函数

$$
形如：f(x)=\sum^{\infty}_{i=0}a_i\cdot \frac{x^i}{i!}
$$
##### 知识1：$ln(1+x) = \sum^{\infty}_{i=1} \frac{(-1)^{i+1}x^{i}}{i}$

##### *环排列生成函数：$-ln(1-x)$

$$
已知n的环排列是：\frac{n!}{n} = (n-1)!\\
那么多项式形式为：f(x) = \sum^{\infty}_{i=1}\frac{i!}{i}\cdot x^i=\sum^{\infty}_{i=1}(i-1)!x^i\\
可以化为指数生成函数：g(x)=\sum^{\infty}_{i=1} \frac{1}{i}\cdot x^i\\
观察知识1，对ln(1+x)简单变形可得到结论
$$

##### *错排生成函数：没有轮换长度1的排列

##### *伯努利数生成函数：$，对于B_0=1，对于(n>0)\sum^{n}_{i=0}C^{i}_{n}B_i = 0$

$$
有：(n+1)!\sum^{n}_{i=0}\frac{1}{(n-i+1)!}\cdot \frac{B_i}{i!} = 0
$$

$$
用j=n-i代入(n+1)!\sum^{n}_{j=0}\frac{\frac{1}{j+1}}{j!}\cdot \frac{B_i}{(n-j)!}=0
$$

$$
那么：生成函数B=\frac{x}{e^x-1}
$$

### 知识2：若一个集合可以看作另一个集合的组合，那么对于被组成的生成函数A，$，B=e^A，A=ln(B)$

### 知识3：牛顿迭代：寻找多项式($mod\space x^n$下)零点

#### *多项式逆元 *多项式$ln$ *多项式带余除法……  弃疗

### 推荐题目：BZOJ3771 : 生成函数(FFT)+容斥，51nod1728：指数型生成函数(告辞型题目)，BZOJ3625：垃圾生成函数，毁我青春(再见型题目)。

Rockdu's Blog

导航

最近发表

大佬们的友链