初探母函数

摘要

本文主要介绍普通母函数及其应用

定义

在数学中,某个序列 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

母函数可分为很多种,包括普通母函数、指数母函数、L 级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。

普通母函数

普通母函数就是最常见的母函数。一般来说,序列 的母函数是

序列 的普通生成函数是 .

指数型母函数

做卷积时可以套出组合数

一组小练习

任务 1

有 1 克、2 克、3 克、4 克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?

鉴于数据范围很小,暴力枚举就可以;这里我们用母函数的方法求解

给一个变量 ,其中指数 表示砝码重量,而系数 表示得到这个重量的方案数

比如 表示 3 克的砝码取 1 枚,目前方案数为 1(在不使用其他砝码的情况下,你只有一种方案)。那么结合加乘原理,并列的决策就相加,然后相乘,我们得到这样的多项式

表示有 1 种方案得到重量为 0 的砝码(即不取);展开上述多项式:

这个多项式的每一项表示的是凑出对应的重量的方案数(其中,你可以选择使用 / 不使用 1,2,3,4 克的砝码一次);比如 表示凑出 5 克重量的方案数为 2,即 1+4 和 2+3.

任务 2

求用 1 分、2 分、3 分的邮票贴出不同数值的方案数,每种邮票有无限个

根据任务 1 的经验,这次的生成函就是无限项的啦。仍然以指数表示数值:

假设我们要求数值为 4 的方案数,那么就把第 4 项的系数算出来就行啦

任务 3

设有 n 个标志为 1,2,…,n 的网袋,第 i 个 网袋里放有 个球。不同网袋里的球是不同的,而同一网袋里的球则是没有差别的,认为是相同的。询问从中取 r 个球的方案数。

这是一个有限项的母函数

那么算出来 的系数就是方案数啦

代码实现也不难,就像高精度乘法一样写就行

等比数列的生成函数

这里讲一个几何级数的展开,即

略证

关于定义域的证明先咕着,这里讲一下生成函数的求解过程

斐波那契通项

我们用母函数来求一下斐波那契数列的通项公式

先看一下该数列的递推式

求解母函数

那么写一个母函数出来:

其中 ,接下来利用递推式求解母函数:

求解完了,那么怎么推导出通项公式呢?那就将它还原成级数啦

求解级数

利用裂项的技巧,做一下代数变换

因为

那么裂项如下

那么根据等比数列的生成函数,里面就是两个等比数列啊!

出现了如此友好的普母函数呢!那么根据普母函数的定义

待续……

参考文献

XSamsara. 生成函数(母函数)——目前最全的讲解。https://blog.csdn.net/qq_41357771/article/details/83449481

WIKIPEDIA. 母函数。https://zh.wikipedia.org/wiki/%E6%AF%8D%E5%87%BD%E6%95%B0

唐小谦。『回答』斐波那契数列通项公式是怎样推导出来的。https://www.zhihu.com/question/25217301


  转载请注明: Sshwy's Blog 初探母函数

 上一篇
金华自闭 Day1 金华自闭 Day1
A. 串20pts 暴力枚举 . 具体来说,我们先枚举 ,然后按等差数列枚举 ,check 一下统计即可 check 失败就 break 40pts其他人好像都是前缀和来着。。。 变换一下枚举顺
2019.02.11
下一篇 
初等数论小结 初等数论小结
摘要 复习一下数论 符号的说明 大 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为,$f(x)=O(g(x
2019.01.26
  目录