母函数简介

简介:  根据定义,这个序列作为函数的系数,称G(x)就是序列的母函数。和一般意义上的函数相比,母函数的功能是计数。 从百度和维基上能找到的相关说明都显得太学院派,不容易理解,还是用例子说明并引入吧。

 

根据定义,这个序列作为函数的系数,称G(x)就是序列的母函数。和一般意义上的函数相比,母函数的功能是计数。

 

从百度和维基上能找到的相关说明都显得太学院派,不容易理解,还是用例子说明并引入吧。

 

有这样一道例题:

 

到这一章为止,已知的计数法则就两种,加法法则(或)和乘法法则(且)。前者是分类思想,后者是分步。

 

法1:分步来看,第一个骰子有1-5种可能,因为两个骰子之和是6,所以一旦第一个骰子确定了,第二个骰子也就随之确定。第一个骰子的每一种可能性都仅对应第二个骰子的唯一确定的点数。因此5*1=5种。

 

法2:分类来看,有可能是1+5=5+1或2+4=4+2或3+3=3+3,累加起来,一共五种可能。

 

当然这个是最最简单的例子,也很容易想,但如果骰子有很多呢?

 

这种情况下,挨个挨个地枚举显然是愚蠢的。而伯努利在300年前已经研究过这个问题了,是关于“投掷m粒骰子时,点数总和为n的可能方案数”,这个问题乍看之下很复杂,令人怀疑人生。

 

那么先从简单情形考虑,两个骰子掷出n点,有多少种可能。这相当于把n拆分成两个数的和,这时候对n枚举就很复杂,所以对两个骰子枚举。第一个骰子,6种可能,相互之间是“或”的关系,对应的是加法,但是不能直接相加,因为这无法反映两个骰子的叠加过程。

我们需要逐个分析一个骰子的不同情况,对于一个骰子,假如掷出2个点,就可以看作一个分步策略,相当于——先掷一个点,再掷一个点,所以是()^2,当然这样不习惯,于是用x^2来表示。那四个点是x^4,因此可以用指数对应点数。

 

这样就可以用(x+x^2+…+x^6)表示一个骰子的投掷过程,对于第二个骰子也是这样,最后两式相乘,x^6前面的系数就是有多少种出现6点的方案。

 

最后的母函数求出来是

 

两个骰子掷出n点的可能方法数就是求G(x)中x^n的系数。实际上系数起了关键性的作用,母函数中的系数对应了计数序列。

 

 

那么回溯到最初伯努利提出的问题,m粒骰子就是m个多项式累乘

 

而要求点数总和为n的可能方案数,也就是求展开式中x^n的系数。这可以看出来,对于这个多项式,我们并不关心它的值,现在关心的却是它的系数了。(所以母函数确实是一位母亲,计数序列作为系数就是她的孩子233)

 

所以母函数的定义我们可以进一步提炼出两点

  1. 关注每一个计数的序列
  2. 每一个计数序列对应的是x^n

而这个定义是拉普拉斯在研究概率的时候,研究了母函数的方法和相关定义。(1812年拉普拉斯在著作《概率的分析理论》第一卷中系统地研究了母函数的方法和有关理论)

 

 

最后总结一下,母函数实际上是用来做什么的,以及它和函数有什么区别。

对于母函数

      • 是计数工具,x的取值我们不关心,似乎只是个占位置的东西
      • 不考虑敛散性
      • 不考虑实际上的函数值
      • 形式幂级数(Formal power series)

 

虽然形式上是函数,但“似函数,非函数”。

 

那——为什么要引入一个母函数呢?因为在现实世界里,对于各种复杂的事件,我们要通过“映射”的方式将其简化,比如说对于分数幂的运算十分困难,我们用一个对数映射将其简化,再求原问题的解,就相对容易了。

 

 

 

在母函数中同样如此,在一开始思考的骰子问题里,直接计算是十分困难的,后来发现通过分步来考虑的时候,把多项式引入,求出相应系数后再对应回来,就得到了解。

 

其实母函数蕴含的就是一种映射关系。

 

那么是什么原因使得母函数具备了计数的法则呢,在骰子那道题中,通过求系数来对应方案数是一个例子。分析一下,对于一般的多项式,可以写成

 

这种形式,展开后的某个幂次的系数可以分为两部分,分别来自于两个括号里的某一项,这实际上就是对应的乘法法则

 

 所以实质上是多项式的乘法运算使母函数具有了计数能力。

 

“母函数就是一列用来展示一串数字序列的挂衣架”

——赫伯特·维尔夫

 

 

相关文章
|
10月前
|
存储 人工智能 算法
【AcWing算法基础课】第四章 数学知识(未完待续)(3)
根据下面公式来预处理出等式右边的组合数的值,那么等式左边就可以用等式右边已经算过的值来进行计算(有点像dp)。
74 0
|
10月前
|
人工智能 算法 BI
【AcWing算法基础课】第四章 数学知识(未完待续)(2)
从2到n枚举每个数,删掉其所有的倍数,枚举完之后,没有被删掉的数为质数。
82 0
|
10月前
|
人工智能 算法
【AcWing算法基础课】第一章 基础算法(部分待更)(3)
输入n个字符串(不含空格),由空格隔开。每行依次输出每个字符串。
72 0
|
10月前
|
算法
【AcWing算法基础课】第五章 动态规划(未完待续)(1)
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且 总价值最大 。
58 0
【AcWing算法基础课】第五章 动态规划(未完待续)(1)
|
10月前
|
人工智能 算法
【AcWing算法基础课】第四章 数学知识(未完待续)(1)
利用秦九韶算法来实现其他进制转十进制的结果求解
66 0
|
10月前
|
人工智能 算法 JavaScript
【AcWing算法基础课】第五章 动态规划(未完待续)(2)
给定一个如下图所示的数字三角形,从 顶部 出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点, 一直走到底层 ,要求找出一条路径,使 路径上的数字的和最大。
51 0
|
10月前
|
存储 算法
【AcWing算法基础课】第一章 基础算法(部分待更)(1)
课上理解算法的 主要思想。 课下 背过(能写出来并调试通过即可) 模板。 提高熟练度方法:一个模板题 重复3~5次 AC通过。
161 0
|
机器学习/深度学习 人工智能 算法
Acwing 算法基础课 c++模板整理(附python语法基础题)(三)
Acwing 算法基础课 c++模板整理(附python语法基础题)
123 0
Acwing 算法基础课 c++模板整理(附python语法基础题)(三)
|
机器学习/深度学习 人工智能 算法
Acwing 算法基础课 c++模板整理(附python语法基础题)(二)
Acwing 算法基础课 c++模板整理(附python语法基础题)
202 0
Acwing 算法基础课 c++模板整理(附python语法基础题)(二)
|
机器学习/深度学习 算法 C++
Acwing 算法基础课 c++模板整理(附python语法基础题)(一)
Acwing 算法基础课 c++模板整理(附python语法基础题)
171 0