算法与组合数学：母函数/生成函数

定义

对于一个序列：$a_0,a_1,a_2,...$ 若构造这样一个函数：

$$G(x)=a_0+a_1x+a_2x^2+...$$

则称，$G(x)$是该序列的母函数/生成函数

例如，$G(x) = (1+x)^n=C_n^0+C_n^1x+C_n^2x^2+...+C_n^nx^n$

是序列$\{C_n^k\},\;\;\;\;\;\;k=0,1,...,n$ 的母函数

易知，该序列还具有排列组合的数学含义。

---

因此，我们常常使用母函数来解决组合问题。

斐波那契与卡特兰数

实例分析

例1：若有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？

考虑构造母函数。

如果用x的指数表示称出的重量，则：

• 1个1克的砝码可以用函数$1+x$表示;
• 1个2克的砝码可以用函数$1+x^2$表示;
• 1个3克的砝码可以用函数$1+x^3$表示;
• 1个4克的砝码可以用函数$1+x^4$表示

Q: 为什么都有个“1+”

A: 表示$x^0=1$,即是不选取该砝码

于是，几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：

$$\;(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}$$

这样就可以根据x的指数得出方案数了，

如：5克的总量有2种（系数）方式组成：5=2+3 和 5=1+4

例2：若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出哪几种重量？各有几种方案？

直接写出母函数：

$$G(x)=(1+x+x^2+x^3)(1+x^2+x^4+x^6+x^8)(1+x^4+x^8)$$

例3：整数n拆分成1，2，3, .…, m的和，求其母函数。

$$G(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+..)(1+x^3+..)... \\=\prod_{i=1}^m(1+\sum_{j=1}^\infty x^{ij})$$

编程实现

与手工展开多项式一样，我们可以对n个多项式乘积先合并前两个括号得到n-1个多项式乘积。于是再对当前的前两个合并，如此往复。

编程实现其实也是如此，比如我们掌握了：

1. 题目要求算到的多项式个数$MAX$
2. 无穷加和下去的极限MAX，即每一个多项式至少加到$x^{i\times n}$.
3. 每一项的系数$\{C_{i\times n}\}$规律

于是，就可以通过合并前两个括号的算法，循环求解实现。

有，合并后x^n^的系数=第一个括号的x^j^系数+第二个括号的x^k^系数，且j+k=n

---

下面以一例题为例给出算法。

求用1分、2分、3分的邮票贴出不同数值的方案数：（每张邮票的数量是无限的）

• 首先转换成母函数求解：

• 1分：(1+x^1^+x^2^+x^3^+x^4^+…)

  2分：(1+x^2^+x^4^+x^6^+x^8^+…)

  3分：(1+x^3^+x^6^+x^9^+x^12^+…)

• 三者相乘

• 注意到：

  1分的第n项x的指数与第n-1项x的指数存在步长为1的递增关系

  2分的步长为2

  依次类推……

#include<cstdio>
typedef long long LL;
const int N = 100 + 5;//假如题目只问到100为止
const int MAX = 3;//题目只有1,2,3这3种邮票
LL c1[N], c2[N];//c2是临时合并的多项式，c1是最终合并的多项式
int n;
void init(){
    c1[0] = 1;//一开始0的情况算一种
    for(int i = 1; i <= MAX; i ++){//把1分到MAXN的邮票合并，变成一个多项式
        for(int j = 0; j < N; j += i){//i分的邮票，步长是i
            for(int k = 0; j + k < N; k ++){//从x^0到x^N遍历一遍
                c2[j + k] += c1[k];//因为j的所有项系数为1，所以c1[k]可以看成c1[k]*1;
            }
        }
        for(int j = 0; j < N; j ++){//把c2的数据抄到c1，清空c2
            c1[j] = c2[j];
            c2[j] = 0;
        }
    }
}
int main(void){
    init();
    while(scanf("%d", &n) != EOF){
        printf("%I64d\n", c1[n]);
    }
}

参考资料

1.ACM数论之旅|镜外之主-博客园