Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
初识生成函数
? 原创 ?
? 生成函数 ?
2018-01-15 21:18:24
640
0
0
rockdu
? 原创 ?
? 生成函数 ?
# 泰勒展开-皮亚诺余项: *本文中$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:垃圾生成函数,毁我青春(再见型题目)。
上一篇:
HDU5629 Clarke and tree
下一篇:
东往之旅——集训咸鱼记
0
赞
640 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册