母函数与掷骰子

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

这是数学家赫伯特·维尔夫(Herbert S. Wilf)对母函数的一个形象且精妙的比喻.

什么是母函数呢？我们将形式幂级数

称为是序列的母函数(又称生成函数, Generating function), 其中幂级数的系数即为序列对应的项.

母函数可分为很多种, 包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数. 这里我们讨论的是普通母函数, 本文也只研究普通母函数.

下面我们通过一个掷骰子问题来说明为什么要定义母函数,并通过用母函数解决掷骰子中的概率问题来体会母函数的奇特之处.

整数分拆

根据题意, 显然点数和序列为递增数列, 所以尽管掷骰子无穷多次, 但数字10只能出现在序列的前10位中.

如果数字10恰好出现在第10位, 这说明, 前10次掷骰子每次的点数都必须是1, 根据独立事件积的概率公式, 可得数字10出现在第10位的概率为.

如果数字10出现在第5位, 说明前5次投掷的点数和是10, 这就相当于将10拆分成5个数相加, 比如. 在数学中, 这被称为整数分拆问题.

整数分拆是指将一个正整数表示为若干个正整数的和. 根据是否考虑分拆部分之间的排列顺序, 整数分拆分为有序分拆和无序分拆.

这是一个古老而又十分有趣的问题. 本文讨论的就是有序分拆问题.

除了枚举, 我们可以将这个问题建模为排列组合中的“隔板”问题, 即10个无区别的球分为5份, 且每份至少有一个球, 则需要用个隔板插入到球之间的个空隙, 因此总共的方案数为.

于是序列第5位出现10的概率为.

母函数

继续讨论, 求数字10出现在序列第2位的概率, 即10的有序2拆分, 这里是否还能套用前面的组合数公式呢？

很遗憾不能, 比如, 在有序拆分中这是有效的, 但是在这个掷骰子问题中, 由于骰子点数不存在7点, 所以这个拆分必须被排除.

让我们来看下面这个式子：

(1)

展开合并同类项后, 项的系数为3, 是由 ,, 合并后得到的.

整数10的有序2-拆分,

对应了幂指数相加,

对应了幂相乘,

而10的2拆分的所有情况数的和对应了多项式同类项合并, 即为(1)式展开合并后项的系数.

将一个骰子投掷1次, 用多项式来表示, 其中项中, 指数对应点数3, 系数1对应在一次投掷中点数3出现1次.

那么将这个骰子投掷n次, 可以表示为

展开后项的系数就是掷骰子n次后, 点数和为m的所有可能情况数.

这里, 多项式 就是序列的母函数.

母函数历史

历史上, 瑞士数学家雅各布·伯努利正是在考虑“当投掷n个骰子时, 加起来点数总和等于m的可能方式的数目”这个问题时首先使用了母函数方法, 并得出可能的数目是 的展开式中项的系数.

之后欧拉在研究自然数的分解时也使用了母函数方法并奠定了母函数方法的基础. 1812年, 法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论.

数学家波利亚将母函数比喻为一个袋子.

母函数是一种类似于袋子的工具. 携带许多零散的小物体可能会令人尴尬, 我们将它们全部放入一个袋子中, 然后我们只需携带一个对象, 那就是这个袋子. — 乔治 波利亚(George Pólya), 《数学与合理推理》(1954)

是的, 母函数中的字母x其实没有什么意义, 重要的是借助多项式的运算解决原问题. 它很好的将复杂的组合问题转化为代数运算, 从而更加高效的解决问题.

母函数求概率

而如果考虑掷骰子时点数出现的概率, 那么掷骰子1次,每个点数出现的概率均为 序列 的母函数就是

展开后项的系数就是掷骰子n次后, 点数和为m的概率.

由于序列表示的是概率, 因此也称为概率密度函数.

回到我们的掷骰子问题, 数字10出现在第2位的概率就是求多项式

展开式中项的系数.

于是, 对于数字10出现的总概率, 就是将数字10出现在前10位的概率求和, 即求多项式

展开后项的系数.

经过编程计算可得结果为.

更多思考

进一步, 我们还可以思考下面这个问题：在点数和序列中, 出现次数最多的是哪个数字(自然数)？概率是多少？

利用前面介绍的母函数方法, 我们可以计算出任意数字出现在序列中的概率, 作出前50个数字出现的概率的条形图, 如图所示

由图可见, 数字6出现的概率最大, 概率为

参考文献：

[1] Eureka Issue 62 | A Journal of the Archimedeans