定义
对于序列 $c_0, c_1, c_2, \cdots$ 构造函数 $G(x) = c_0 + c_1x + c_2x^2 + \cdots$,称 $G(x)$ 为母函数
,又叫生成函数。
组合数学的主要内容是计数,用的最多的工具要算母函数。
例:两个骰子掷出总和为 $6$ 点,有多少种可能?
解法1:第一个骰子掷出 $1 \sim 5$ 点,且第二个骰子掷出的点数由第一个骰子确定
解法2:$1+5 = 5+1$ 或 $2+4 = 4+2$ 或 $3+3 = 3+3$
雅各布 $\cdot$ 伯努利提问:
投掷 $m$ 粒骰子时,加起来点数总和等于 $n$ 的可能的方式的数目?
两个骰子掷出 $n$ 点,有多少种可能?
$(1$点或 $2$ 点或 $3$ 点或 $4$ 点或 $5$ 点或 $6$ 点$)$
这里为了方便,可以将点替换为 $x$。这样做的好处是先加一个 点,再加一个点,由于投掷是分部的过程,合并之后就可以用 $x^2$ 来表示
我们可以发现对应于 $x^k$ 进行相乘,它就可以表示出来骰子的投掷过程
因此,用指数可以对应点数
于是我们可以用 $x + x^2 + x^3 + x^4 + x^5 + x^6$ 来代表一个骰子的投掷过程
这样一来,我们可以用两个多项式的相乘来代表两个骰子的投掷,即
$ (x + x^2 + x^3 + x^4 + x^5 + x^6) \times (x + x^2 + x^3 + x^4 + x^5 + x^6) $
这时我们要去求 $x^6$ 前面的系数就是代表了有多少种出现了有 $6$ 点的方式
$ x^6:\ x^1 \cdot x^5 + x^2 \cdot x^4 + x^3 \cdot x^3 + x^4 \cdot x^2 + x^5 \cdot x^1 = 5x^6 $
$x^6$ 的系数是 $5$,表示两个骰子掷出 $6$ 点的可能方法有 $5$ 种
$ G(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^2 = x^2 + 2x^3 + 3x^4 + 4x^5 + \color{red}{5}x^6 + 6x^7 + 5x^8 + 4x^9 + 3x^{10} + 2x^{11} + x^{12} $
于是,两个骰子掷出 $\color{red}{n}$ 点的可能方法数即为求 $G(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^2$ 中 $x^6$ 的系数。
从这里可以发现系数起了关键作用,函数中的系数对应计数序列。
从上面的叙述中可知,每一粒骰子的投掷过程都可以用一个多项式来表示,那么对于伯努利问题中的 $m$ 粒骰子呢?
我们自然可以拿多项式的累乘就可以得到,也就是 $G(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^m$
伯努利想知道加起来总和等于 $n$ 有多少种方式,那就意味着我们想求这个 $G(x)$ 的展开式中 $x^n$ 前面的系数
综上可知,母函数确实是一个函数,也是一个多项式,但我们并不关心这个多项式的值,我们现在关心的却是它的系数了
所以可以看出母函数确实是一位母亲,而计数的序列作为函数的系数就是它的孩子
母函数的定义:
- 关心每一个计数的序列
- 每一个计数序列对应的是 $x^k$
母函数的概念是何时提出的?
$1982$ 年,法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论。
母函数:
- 计数工具
- 不考虑收敛性
- 不考虑实际上的数值
- 形式幂级数($Formal \ power \ series$)
于是,我们可以说母函数似函数、非函数。
母函数和计数法则
映射关系
实际上在骰子的投掷问题出现困难之后,我们不再进行直接的求解,而通过去对应它的多项式乘法来求系数,这样就转换成了求序列的问题。那么是如何能够实现这样一个对应关系的呢?
因此我们可以看到,虽然只是我们非常熟悉的多项式乘法,其中却蕴含了乘法法则和加法法则,正是多项式这样的乘法运算使得母函数具备了计数的能力
什么是母函数?
其实有一位数学家叫做赫伯特 $\cdot$ 维尔夫,曾经用一句非常经典的话概括了母函数是什么
母函数就是一列用来展示一串数字序列的挂衣架。
回顾一下函数与母函数的发展历史
母函数的简单应用
现在有 $4$ 个砝码,每个砝码都有不同的重量:$1g$、$2g$、$3g$、$4g$
问:利用这 $4$ 个砝码一共能称出多少种重量?对于某一个重量,它有多少种不同的方案呢?
$ \begin{aligned} G(x) &= (1+x)(1+x^2)(1+x^3)(1+x^4)\\\ &= 1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \end{aligned} $
所以我们可以称出 $1g \sim 10g$
那么对应于每种重量有多少种方案呢?
例如右端有 $2x^5$ 项,即称出 $5g$ 的方案有 $2$ 种
例如右端有 $x^{10}$ 项,即称出 $10g$ 重量的方案有 $1$ 种
普通生成函数
生成函数(Generating Function)
某个序列 $a$ 的生成函数是一种形式幂级数
,其每一项的系数可以提供关于这个序列的信息。
根据问题的不同,可以构造不同形式的生成函数。
包括普通生成函数
、指数生成函数
、狄利克雷生成函数
等。
普通生成函数:$F(x) = \sum\limits_{n \geqslant 0} a_nx^n$
$\{ a_n \}$ 可以是有穷序列,也可以是无穷序列。例如,
序列 $(1, 2, 3)$ 的普通生成函数是 $1+2x+3x^2$
序列 $(1, 1, 1, \cdots)$ 的普通生成函数是 $1 + x + x^2 + \cdots = \sum\limits_{n \geqslant 0} x^n$
序列 $(1, 2, 4, 8, \cdots)$ 的普通生成函数是 $1 + 2x + 4x^2 + \cdots = \sum\limits_{n \geqslant 0} 2^n x^n$
加减运算
$F(x) \pm G(x) = \sum\limits_{i \geqslant 0} a_ix^i \pm \sum\limits_{j \geqslant 0} b_jx^j = \sum\limits_{n \geqslant 0} (a_n \pm b_n) x^n $
因此 $F(x) \pm G(x)$ 是序列 $(a_n \pm b_n)$ 的普通生成函数
乘法运算(卷积)
$ F(x)G(x) = (\sum\limits_{i \geqslant 0} a_ix^i) \cdot (\sum\limits_{j \geqslant 0} b_jx^j) = (\sum\limits_{n \geqslant 0} x^n) \cdot (\sum\limits_{i=0}^n a_ib_{n-i}) ~(\text{令} i+j=n) $
例如 $n = 3$,则 $x^3$ 的系数为 $a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0$
因此 $F(x)G(x)$ 是序列 $(\sum\limits_{i=0}^n a_ib_{n-i})$ 的普通生成函数
普通生成函数
可以用来解决多重集组合数
问题。
问题
:有 $n$ 种物品,每种物品有 $a_i$ 个,问取 $m$ 个物品的组合数?
多重集组合数
设从每种物品中取 $b_i$ 个,$0 \leqslant b_i \leqslant a_i$,$m = \sum\limits_{i=1}^n b_i$,对于一组选定的 $b_i$ 进行组合的方案数为 $1$。
例如,取 $3$ 个 $A$,$1$ 个 $B$ 的方案就是 $\{AAAB\}$;取 $2$ 个 $A$、$2$ 个 $B$ 的方案数就是 $\{AABB\}$
那么,所有满足 $b_1 + b_2 + \cdots + b_n = m$ 的方案之和,即答案。
构造普通生成函数
第 $1$ 种物品的生成函数为 $1 + x + x^2 + \cdots + x^{a_1}$,第 $n$ 种物品的生成函数为 $1+x+x^2+\cdots + x^{a_n}$
即 $(1 + x + x^2 + \cdots + x^{a_1})(1 + x + x^2 + \cdots + x^{a_2}) \cdots (1 + x + x^2 + \cdots + x^{a_n})$,求 $x^m$ 的系数。
注意:指数
即物品个数,系数
即组合数。
例如,有三种物品,分别有 $3, ~2, ~1$ 个,问取 $4$ 个物品的组合数?
枚举的话,有 $\{AAAB, AAAC, AABB, AABC, ABBC\}$ $5$ 种方案。
$ \begin{align} &(1+x+x^2+x^3)(1+x+x^2)(1+x)\\\ =& (1+x+x^2{\color{Red} +} x+x^2+x^3 {\color{Red} +} x^2+x^3+x^4 {\color{Red} +} x^3+x^4+x^5)(1+x)\\\ =& (1+2x+3x^2+3x^3+2x^4+x^5)(1+x)\\\ =& (1+x {\color{Red} +} 2x+2x^2 {\color{Red} +} 3x^2+3x^3 {\color{Red} +} 3x^3+3x^4 {\color{Red} +} 2x^4+2x^5 {\color{Red} +} x^5+x^6)\\\ =& 1+3x+5x^2+6x^3+5x^4+3x^5+x^6 \end{align} $
例题1:HDU2152 Fruit
有 $n$ 种水果,每种水果选购的个数在 $[a_i, b_i]$ 之间,问买 $m$ 个水果有多少种购买方案?
算法分析
构造生成函数
$ (x^{a_1} + \cdots + x^{b_1})(x^{a_2} + \cdots + x^{b_2}) \cdots (x^{a_n} + \cdots + x^{b_n}) $
求 $x^m$ 的系数。
例如,选购的个数 $[2, 3], [0, 2], [1, 2]$
$ \begin{align} &(x^2+x^3)(1+x+x^2)(x+x^2)\\\ =& (x^2+x^3+x^4 {\color{Red} +} x^3+x^4+x^5)(x+x^2)\\\ =& (x^2+2x^3+2x^4+x^5)(x+x^2)\\\ =& x^3+x^4 {\color{Red} +} 2x^4+2x^5 {\color{Red} +} 2x^5+2x^6 {\color{Red} +} x^6+x^7\\\ =& x^3 + 3x^4 + 4x^5 + 3x^6 + x^7 \end{align} $
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
const int MX = 105;
int n, m;
int a[MX], b[MX], c[MX], d[2*MX];
int f() {
memset(c, 0, sizeof c);
memset(d, 0, sizeof d);
for (int i = a[1]; i <= b[1]; ++i) c[i] = 1;
for (int i = 2; i <= n; ++i) {
// 计算 x^j*x^k 的系数
for (int j = 0; j <= m; ++j) {
for (int k = a[i]; k <= b[i]; ++k) {
d[j+k] += c[j];
}
}
for (int j = 0; j <= m; ++j) {
c[j] = d[j];
d[j] = 0;
}
}
return c[m];
}
int main() {
while (cin >> n >> m) {
rep(i, n) cin >> a[i] >> b[i];
cout << f() << '\n';
}
return 0;
}
例题2: HDU1085 Holding Bin-Laden Captive!
面值为 $1, 2, 5$ 的硬币分别有 $a_1, a_2, a_3$ 枚,问用这些硬币不能组成的最小面值是多少?
算法分析
构造生成函数
$ (1+x+x^2+\cdots + x^{a_1})(1+x^2+x^4+\cdots+x^{2a_2})(1+x^5+x^{10}+\cdots+x^{5a_3}) $
从小到大遍历系数,等于 $0$ 的那一项就是答案
例如,$1$ 分有 $1$ 枚,$2$ 分有 $1$ 枚,$5$ 分有 $1$ 枚
$ \begin{align} &(1+x)(1+x^2)(1+x^5)\\\ =& (1+x^2{\color{Red} +} x+x^3)(1+x^5)\\\ =& (1+x+x^2+x^3)(1+x^5)\\\ =& 1+x^5{\color{Red} +} x+x^6{\color{Red} +} x^2+x^7{\color{Red} +} x^3+x^8\\\ =& 1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8 \end{align} $
所以不能组成的最小面值为 $4$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
const int MX = 8005;
int n, m;
int a[4], b[4], c[MX], d[2*MX];
void f(int m) {
memset(c, 0, sizeof c);
memset(d, 0, sizeof d);
for (int i = 0; i <= a[1]; ++i) c[i] = 1;
for (int i = 2; i <= 3; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= a[i]*b[i] and j+k <= m; k += b[i]) {
d[j+k] += c[j];
}
}
for (int j = 0; j <= m; ++j) {
c[j] = d[j];
d[j] = 0;
}
}
}
int main() {
while (cin >> a[1] >> a[2] >> a[3]) {
if (a[1]*a[1] + a[2]*a[2] + a[3]*a[3] == 0) break;
b[2] = 2, b[3] = 5;
int m = a[1] + a[2]*2 + a[3]*5;
f(m);
int x = 1;
while (x <= m and c[x]) x++;
cout << x << '\n';
}
return 0;
}