专栏首页算法码上来具体数学-第14课(牛顿级数和生成函数)

具体数学-第14课(牛顿级数和生成函数)

原文链接:

具体数学-第14课 - WeiYang Bloggodweiyang.com

牛顿级数

多项式函数的一般表示形式为:

也可以将其表示为下降阶乘幂的形式:

这种表示的好处是,求差分更加方便:

因为有

所以多项式又可以表示为组合数的形式,也被叫做牛顿级数:

这种形式的差分也特别简单,因为有

所以

阶差分可以写为:

所以有:

所以牛顿级数又可以写为:

这个形式是不是很像泰勒展开?

生成函数

对于无限序列

,定义它的生成函数为:

定义一个函数用来表示

的系数:

两个生成函数相乘的结果为:

考虑下面的二项展开:

可以发现这就是序列

的生成函数。 替换变量可以得到:

两个式子相乘可以得到:

等式两边

的系数相等,于是:

这和上节课讲到的范德蒙德卷积公式类似!这里是用生成函数证出来的。

同理根据

可以得到

下面是一个重要的生成函数:

它其实就是序列

的生成函数。

生成函数应用

那么生成函数有什么应用呢?一个很重要的应用就是用来求解递归式。

例如大家很熟悉的斐波那契数列:

首先为了统一表示,将递归式改写为如下形式:

然后两边同时乘以

,得到:

两边对指标

同时求和,可以得到:

所以

最后只要将

表示成多项式的形式就行了,

就是斐波那契数列的通项公式了。

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 556】下一个更大元素 III

    给定一个32位正整数 n,你需要找到最小的32位整数,其与 n 中存在的位数完全相同,并且其值大于n。如果不存在这样的32位整数,则返回-1。

    godweiyang
  • 论文赏析[TACL19]生成模型还在用自左向右的顺序?这篇论文教你如何自动推测最佳生成顺序

    大多数的生成模型(例如seq2seq模型),生成句子的顺序都是从左向右的,但是这不一定是最优的生成顺序。可能有人要说,反正最终都是生成一个句子,跟生成顺序有啥关...

    godweiyang
  • 每日算法系列【LeetCode 926】将字符串翻转到单调递增

    如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增...

    godweiyang
  • Python学习笔记九(变量作用域及内置函数和闭包函数)

    在上次的学习中,初步认识了Python的自定义函数方式及变量参数。那么编程中的局部变量和全局变量应该是大多数语言的标配。Python中如果定义局部变量和全局变量...

    世纪访客
  • 我们能用云函数做什么?

    现如今云计算时代渐渐出现了越来越多的新型模式,从IaaS、PaaS、SaaS到CaaS,再到的微服务架构,都在试着将各种软、硬件资源或抽象的事物做为一种服务提供...

    YingJoy_
  • Python学习(三)---- 集合、文件操作、字符编码和函数

    https://blog.csdn.net/fgf00/article/details/52167245

    智能算法
  • Jquery Ajax请求文件下载操作失败的原因分析及解决办法

    jQuery确实是一个挺好的轻量级的JS框架,能帮助我们快速的开发JS应用,并在一定程度上改变了我们写JavaScript代码的习惯。

    用户5640963
  • 干货 | MIT手把手教你一步步创建自己的R程序包

    大数据文摘
  • 麻省理工三位教授教你一步步创建自己的R程序包(附完整教程下载)

    大数据文摘
  • [译]精通JavaScript面试之什么是函数式编程?

    在JavaScript的世界中函数式编程已然变成热门的话题了。仅仅在几年之前,极少数的JavaScript程序员听说过函数式编程是什么,但是在过去三年里我看到的...

    the5fire

扫码关注云+社区

领取腾讯云代金券