【乐正垂星】母函数是可以被理解的？！

1.问题引入：

给定一个大小为n的集合a，求a的子集中有多少个的元素和为k。

（0）暴力：枚举每个子集再求和，时间复杂度约为O（n*2^n），几乎不可接受。

（OI生：这还不简单，背包模板题）

（1）正解：构建母函数

F(x)=(1+x^a1)(a+x^a1)……(1+x^an)

将其乘开，其中x^k项的系数即为答案。

（2）合理性证明：在乘开的同时，本质上就是在枚举所有的子集。

2.母函数的推导过程

（0）概念理解：x的意义

也许有人会跟你说x是没有意义的，但是实际上，“x虽然不是一个具体的数，但并不抽象”。（请先三连）

（1）第一节 加法原理和乘法原理

以集合{1,2,3,4,5}为例。对于1，有选或不选共（1+1）种情况。同理，对于另外4个元素都是如此。因此，该集合的子集个数为

(1+1)(1+1)(1+1)(1+1)(1+1)=32

（包括空子集）

仔细观察，这个式子与我们之前得出的母函数的形式几乎完全一致：

本质上，(1+1)……(1+1)就是

（选1或不选1）和（选2或不选2）……（选5或不选5）

同时，我们的母函数也是这样如此构造出来的。因此，这两个式子同构（这里是不是说得太简略了一点）。

或 与 和，是有分配律的。

（Tips：这里的“或”与“和”与bool运算中的概念没什么关系，只是名字差不多，切勿搞混了）

形象的展开：两者同构性得证（《数学频道》）

但是，当我们把函数变为

F(x)=(1+a1)(1+a2)……(1+an)时，没法算出来特定和的子集个数，而是所有子集的和（为什么答案是所有子集之和，我会在笔记最后说明）

原因分析：加法变成了乘法。

因此我们需要寻找一种方法，能够将乘法运算变为加法运算，“正巧，指数运算就有这种性质”。也正是因此，x取任何数都无所谓。但是通过“x什么也不表示”来推导“x没有意义”，是颠因为果的。

母函数出现了。

（2）不同的母函数（母函数的推广）

将 “或” 与 “和” 推广，运用结合律，可以得到如下的式子：

这与母函数形式及其相似。

原因：+ → 或 ，X → +1，x → 和，这三者是同构的，只有名称上的区别。

（这小写的x怎么跟乘号一模一样啊）

新的问题：计算有3个元素的子集的个数

（注意，我们要用母函数的方式推导，而不是直接用组合数）

推导过程视频说得已经很清楚了。我简单概括一下：先计算出每个数字的加入或不加入的影响，再以“和”运算（即乘法）连接，就得到了——

这也说明了，每一个组合数都是二项式的对应系数。

（3）数列

对于一个数列a，该数列的母函数为

P(x)=a0x^0+a1x^1+a2*x^2……

例：求斐波那契数列的通项公式：

得出F(x)=1/(1-x-x^2)，展开，得到其通项公式。

数列part：

用一个数列定义另一个数列（不推荐）：

以{bn}={S(a)n}来表示。这里S就不是一个什么数字了，而是类似于一个函数，称作移位算子。

常见的有：

于是，嗯——

能不能像之前处理x那样处理S呢？

可不可以安心地用麦克劳林展开呢？

对于任意的多项式，都有其唯一的逆。除以一个多项式，就相当于乘其逆（怎么有乘法逆元那味儿了）

因此，上面问题的答案均为是。

3.后记：

技术总结：一键三连。

结尾补充：

为什么对于任意的集合a，其中所有元素与1之和的乘积一定是a的所有子集的元素和呢？

对于第i个元素，不取时，贡献为*1；当取时，贡献即为*ai。

轻松得证。

（本蒟蒻第一次写这么长的笔记，定然有错误，有不足，请各位dalao指教）