生成函数（母函数）解决组合问题

发表于 | 分类于

生成函数（母函数）

一、普通生成函数解决组合问题

我认为生成函数解决组合问题就是把问题转换成二项式或递推关系问题的方法
问题

用1元、5元、10元三种纸币能拼出多少种100元的方案？

这其实是一个组合问题，用三种纸币组合成100元
这种题用生成函数来做就很方便
下面我们来分析这道题

  • 分析1元硬币的使用情况（五元十元可类比）

      一元硬币在最终的方案中可能用到0次、1次、2次.......

    好，接下来，我们尝试将这个问题转换成二项式问题
    我们将0次写为$x^0$,1次写为$x^1$,2次写成$x^2$
    则，针对1元硬币的所有情况就可以表示为$A=x^0+x^1+x^2…$
    类比到其他两种硬币：
    五元硬币：$B=x^0+x^5+x^{10}…$
    十元硬币：$C=x^0+x^{10}+x^{20}…$
    所以硬币组合的所有情况就是将以上三个多项式相乘
    $AllCount=(x^0+x^1+x^2…)(x^0+x^5+x^{10}…)(x^0+x^{10}+x^{20}…)$
    稍微观察可知，给出一个 和n，则多项式展开后的$x^n$项的系数就是组合成n的组合的数量，我们现在想把它化成一个$(m+x)^n$的形式，这样我们就可以用二项式的系数公式解决问题了。
    但是，我们不可能全部打开计算，那就是穷举了，所以要利用数学知识来解决这个问题
    观察一元硬币的表达式，明显是等比数列，则可利用等比数列求和公式得到

$A=\displaystyle\frac{1-x^n}{1-x}$

我们再来化简这个式子，我们知道x的取值实际上是没有意义的，所以为了化简，我们规定 0< x <1

所以可得：

$A=\displaystyle\frac{1}{1-x}$
类比得：
$B=\displaystyle\frac{1}{1-x^5}\ \ \ \ C=\displaystyle\frac{1}{1-x^{10}}$

这个时候我们发现ABC不能化简成一个二项式的形式，也就是说不能用组合数来表示第N项前面的系数
所以我们转而求其递推式$D_n$
A式不动，仍旧表示只用1元硬币的情况，我们来分析一下A中的系数表示
由于$A*(1-x) = 1$得到$A-Ax = 1$说明$A_n=A_{n-1} (A_n表示A式指数为n项的系数）$
这是为什么呢？由于$Ax$可以看做将A的每一项指数加1，相减后剩下第一项$x^0$，后面的项都减没了，说明n-1项的系数与n项的系数是一样的即：$A_n=A_{n-1}$
接下来用同样的方法处理，我们用N式表示用1元和5元的情况,D式表示全用的情况即：

$N = （x^0+x^5+x^{10}...）A$

$D = （x^0+x^{10}+x^{20}...）N$

我们处理一下上式：

$N(1-x^5)-A=0 $ 打开得 $N-Nx^5-A=0$

得：
$N_n -N_{n-5}-A_n=0$

同理可得：
$D_n -D_{n-10}-N_n=0$

这样我们就得到了一个递推关系式：

$D_n = D_{N-10}+N_n$ $N_n =N_{n-5}+A_n$ $A_n = A_{n-1} = 1$

按照此递归关系式可以得到线性时间的$D_n$算法
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "stdafx.h"
#include <iostream>


int gene5(int n) {
	if (n < 5) return 1;
	else return gene5(n - 5) + 1;
}

int generation(int n) {
	if (n < 5) { return 1; }
	else if(n<10)return gene5(n);
	else return generation(n - 10) + gene5(n);
}

int main()
{

	std::cout<<generation(100);

	return 0;
}

二、指数生成函数助攻解决排列问题

我们搞定了组合问题，但是组合问题的解决方法不能解决排列问题，比如说：

拿6个球，有红球绿球，有多少种方法？

我们来看一下区别，之前钱的问题没有顺序一块和五块哪个先挑出来是无所谓的的因素，这次红绿之间有顺序的问题

这样我们就没办法用之前的方法来操作了，这时候，我们用到了拉普拉斯提出的另一种生成函数——指数生成函数

指数生成函数的一般形式是$x+\displaystyle\frac{1}{2!}x^2+\displaystyle\frac{1}{3!}x^3…$
处理最后得出的生成函数表达式时要化成这样的基本形式，每项前写上它的系数(不理解看后面)

我们来看一下与常规生成函数的区别，式子的每一项的指数 n 还是代表选择 n 个绿（红）球
如果没有条件约束，两个式子乘起来就是绿球和红球能抽出的所有情况的生成函数
但是跟常规生成函数的区别在于，每一项前面多出了一个常数项$\displaystyle\frac{1}{r!}$
这个数有什么用呢？

我猜想它跟组合数有关系，你想要把排列的方案数显示在生成函数中，必须做点什么，我们来看看它到底做了什么才能把组合数巧妙地融合进生成函数中

先来看看我们想要什么，对于某个确定的n（球的总数），当绿球取r个，红球取n-r个时，我们想要的结果是$\sum\limits_{r=0}^n{C^r_n}$

明确答案后我们来看一个例子
如果是三个球的组合排列，两个红球和三个绿球组成的排列中，对应的项$\displaystyle\frac{1}{2!}x^2$与$\displaystyle\frac{1}{3!}x^3$乘积再化成$x^5$对应的形式

$\displaystyle\frac{10}{5!}x^5$

那么10就是两个红球和三个绿球的方案数，初见很神奇，看一下其中的原理，我们知道：

$C^r_n = \displaystyle\frac{n!}{r!(n-r)!}$

而$\displaystyle\frac{1}{2!}x^2$和$\displaystyle\frac{1}{3!}x^3$分别是$\displaystyle\frac{1}{r!}x^r$和$\displaystyle\frac{1}{(n-r)!}x^{n-r}$(n=5,r=2)

他们的乘积可以化成:

$\displaystyle\frac{\displaystyle\frac{n!}{r!(n-r)!}}{n!}x^n$

分子就是我们要求的方案数。

这时候我们验证了从数学上来看这个公式的合理性，我们再想一想，它的物理意义究竟是什么？
最终方案数的多少，可以用组合的和来表示，n!代表了针对一个组合所有排列的合计，而$\displaystyle\frac{1}{r!}x^r$中的$\displaystyle\frac{1}{r!}$用来消除重复的方案数，也就是绿色或红色自己本身的排序。

三、求解任意常系数k阶齐次递推关系

四、一些例子和总结

…未完