母函数简介

简介:  根据定义,这个序列作为函数的系数,称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)

 

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

 

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

 

 

 

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

 

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

 

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

 

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

 

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

 

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

——赫伯特·维尔夫

 

 

相关文章
|
7月前
|
机器学习/深度学习 资源调度 数据可视化
UCB Data100:数据科学的原理和技巧:第十六章到第十八章
UCB Data100:数据科学的原理和技巧:第十六章到第十八章
125 0
|
7月前
|
机器学习/深度学习 SQL 移动开发
UCB Data100:数据科学的原理和技巧:第十三章到第十五章
UCB Data100:数据科学的原理和技巧:第十三章到第十五章
92 0
|
7月前
|
数据可视化
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(1)
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(1)
89 0
|
7月前
|
机器学习/深度学习 数据可视化 Linux
UCB Data100:数据科学的原理和技巧:第六章到第十章(3)
UCB Data100:数据科学的原理和技巧:第六章到第十章(3)
81 0
|
7月前
|
数据可视化 Linux 定位技术
UCB Data100:数据科学的原理和技巧:第六章到第十章(4)
UCB Data100:数据科学的原理和技巧:第六章到第十章(4)
144 0
|
7月前
|
JSON 数据可视化 安全
UCB Data100:数据科学的原理和技巧:第六章到第十章(1)
UCB Data100:数据科学的原理和技巧:第六章到第十章(1)
107 0
|
7月前
|
数据可视化 Python
UCB Data100:数据科学的原理和技巧:第六章到第十章(2)
UCB Data100:数据科学的原理和技巧:第六章到第十章(2)
85 0
|
7月前
|
分布式计算 数据可视化 内存技术
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(2)
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(2)
76 0
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(2)
|
7月前
|
分布式计算 数据可视化 内存技术
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(3)
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(3)
50 0
UCB Data100:数据科学的原理和技巧:第十一章到第十二章(3)
|
7月前
|
机器学习/深度学习 数据可视化
UCB Data100:数据科学的原理和技巧:第六章到第十章(5)
UCB Data100:数据科学的原理和技巧:第六章到第十章(5)
70 0