当前课程知识点:组合数学 >  初识母函数 >  母函数是函数的母亲吗 >  母函数的定义(1)

返回《组合数学》慕课在线视频课程列表

母函数的定义(1)在线视频

下一节:母函数的定义(2)

返回《组合数学》慕课在线视频列表

母函数的定义(1)课程教案、知识点、字幕

你知道什么是母函数吗

知道 母函数是函数的妈妈

那你知道是什么是函数吗

函数是母函数的宝宝

如果用色子来说 你知道什么是母函数吗

那就是好几个色子合在一起是母函数吧

对呀 那你喜欢母函数还是喜欢函数啊

母函数

为什么呀

因为母函数比函数要长得大

哦 真好

说起函数 大家肯定特别的熟悉

因为我们学函数学了很多很多年了

那么我们来看这样一个式子

这是一个非常长的多项式

一般我们叫它什么呢

我们叫G(x)就是一个函数

那么今天呢我们学什么呢

我们今天学的名字和函数非常相似

叫做母函数

那么大家都会想

什么是母函数呢

我们不如打开教材看一下

我们翻到第二章 定义2.1是这样描述的

它说对于一个序列c0 c1 c2

我们构造一个函数G(x)

等于c0加上c1x加c2x平方 一直累加下去

称G(x)为序列c0 c1 c2的母函数

从这个概念上来看

我们发现母函数是什么呢

不也就是一个多项式吗

我们看到的它说到的是有一个序列

这个序列作为函数的系数

称这个函数就是序列的母函数

这么一比较

怎么母函数和函数长得是一模一样呢

那么到底有什么区别呢

母函数到底还是不是函数呀

我们又看书上有这样一句话

它说组合数学主要是要计数

用的最多的工具是母函数

函数我们用来干什么的

函数我们用来求极值

我们用来求x自变量的取值范围

我们要分析的它的收敛性

但是在组合数学中

我们用母函数是用来计数的

那么我们又觉得这到底是怎么一回事儿呢

回头我们又查了一下百度和维基百科

它们上面都说到组合数学中的母函数

就是计数的重要工具

尤其它在概率论和计数中是一种重要的方法

说到这儿我们更加的糊涂了

到底这个母函数是用来做什么呢

我们不如拿一个例子来看一看

今天呢 我们用色子的投掷

给大家讲什么是母函数

我们来研究一下

如果我投掷两粒色子

最后两个色子加起来的总和是六点

能有多少种可能性呢

那实际上就相当于第一个色子

和第二个色子加起来和值等于六

那么我们现在所知道的计数方法

无非就是基本的乘法法则和加法法则

它对应的就是分类的思想和分步的思想

在这里我们也是一样

比如说我是不是可以分步来看呢

第一个色子能有多少种可能性呢

第一个色子它甩出来的时候

一二三四五 只有五种可能性

那么一旦第一个色子确定了

因为两个色子之和是确定的六

所以呢 第二个色子随之也确定了

因此第一个色子有五种方法

第二个色子只有一种方法

五乘以一等于五

这自然说我原来掷出六点

只可能有五种可能性

另外我还可以分类来看啊

比如说它有可能是一加上五

有可能是五加上一

有可能是二加四 四加二

有可能两个还都是三

那么每一种方法我们累加起来

发现它就一共是五种

这个问题虽然很简单

用到的也是最最基本的乘法法则和加法法则

但是我们如果色子有这么多呢

大家觉得该怎么去计算呢

难道还要挨个挨个去枚举吗

其实啊 在三百年前伯努利就已经研究了

这么多色子的问题

他当时问如果我投掷m粒色子出去

加起来点数总和等于n的所有可能方式

有多少种

我想同学们在这里面似乎就有点茫然了

该怎么做呢

我们现在研究是相对简单的一个例子

只有两个色子

那么只有两个色子如果掷出n点的话

有多少种可能性呢

我们就相当于把整数n

拆分成两个自然数之和

这时候由于n的存在

我们再进行枚举的话

相对来说就比较复杂了

我们只能一个色子一个色子来看

这时候先看第一个色子

它能出现多少个点呢

一点两点三点四点五点六点

它们之间是或的关系

那么在或的关系里面

我们会发现 或 实际上对应的是加法

那应该把什么东西加到一起呢

我们如果把点数直接相加的话

那么它直接就累加了

并不能实现两个色子的累加过程

我们在逐个分析一个色子

对于这一个色子我们可以看到

它如果有两个点的话

也可以看作一个分步的策略

先添一个点 再添一个点

这时候有相当于有两个点进行相乘

也可以表示成点的平方

当然点的平方我们并不习惯

我们可以用x平方来表示

如果这个两个点是x平方

那么四个点就可以是x四次方

第一个色子x平方

第二个x四次方

它们之间投掷是分步的过程

因此合并之后就得到了一个x六次方

这时候我们发现

实际上对应于x的k次方进行相乘

它就可以表示出来色子的投掷过程

因此用指数可以对应点数

因此这时候我们就可以用x加x平方

一直加到x六次方这样一个多项式

来代表一个色子的投掷过程

同样对于第二个色子也有类似的一个式子

第一个色子第二个色子

分步的策略我们就可以用乘法

用两个多项式相乘来代表色子的投掷

这时候我们要去求x的六次方

前面的系数实际上就是代表了

有多少种出现了有六点的方式

比如说 对于第一个色子一个点

第二个色子五个点

实际上我们就得到了x一次方乘以x五次方

对应的这样一个系数

同样两点四点三点三点四点两点五点一点

这样一个枚举过程

实际上就是我们在做多项式乘法

而它得到的系数

就是对应能够得到六点的系数

也就是方案数

那么对于这样一个多项式乘法

把它转化成一个函数形式

就相当于G(x)等于x加x平方

一直加x六次方的平方

展开式中它们的系数就代表了

x的n次方的系数就是两个色子

掷出n点的可能方法数

从这里面我们就会发现

实际上系数起了关键的作用

它可以在函数的运算中对应计数的序列

通过刚才的分析我们知道了

每一粒色子都可以用一个多项式来表示

那么对于伯努利问题中m粒色子呢

我们自然可以拿多项式累乘就可以得到

因此对于投掷m粒色子的时候

它可以用G(x)等于x加x平方加x三次方

一直加到x的六次方的m次方来表示

那么伯努利想要知道

加起来的点数总和等于n有多少种方式

那就意味着我们想求这个G(x)里面

x的n次方前面的系数

走到这里我们会发现

确实这是一个函数

这是一个多项式

但是呢 我们并不关心这个多项式的值

我们现在关心的却是它的系数了

所以可能看到母函数确实是一位母亲

但是谁是孩子呢

计数的序列作为函数的系数就是它的孩子

所以母函数的定义是这样的

首先我们应该关注每一个计数序列

而每一个计数序列对应的是x的k次方

这时候我们把它累加起来

就构成了一个函数

这个函数和传统的函数意义不同

因为我们关注的是它的系数

因此这就是母函数的定义

那么母函数的定义是谁提出的呢

实际上是拉普拉斯在他研究概率的时候

研究了母函数的方法和有关的定义

回头我们看 实际上母函数是为了干什么呢

它和函数有什么区别

首先母函数它是用来计数的

传统的函数我们要考虑x的取值范围

而在这里x取值是什么

我们并不关心

同时 原来的函数中我们要考虑它是否收敛呀

它是否有极值

在这里面x似乎就是一个占位置的地方

我们根本不在乎它取什么

也不在乎G(x)最终能够达到多少数值

所以我们会看到

虽然这形式上仍然是一个函数的样子

但是母函数似函数非函数

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

母函数的定义(1)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。